# 題目: UVa 315 - Network

# 題目說明

給一個點皆連通的無向圖
割點(Articulation Points 的數量

割點定義:

  1. 對於 root ,如果 root 有兩顆以上的 subtree ,那 root 為割點
  2. 對於非 leaf 的其他節點,其 child 沒有一條 back edge 指到 ancester ,則該點為割點

INPUT:
每筆測資第一行有一個整數 N ,代表有 N 個節點
N = 0 時結束程式
接下來有最多 N 行,每行有數個整數
例如 5 1 2 3 4 代表有四個邊 (5, 1)、(5, 2)、(5, 3)、(5, 4)


OUTPUT:
輸出 Articulation Points 的數量。

# 解題方法

先建圖 (為無向圖,所以建雙邊)
之後跑 dfs ,紀錄每個點的 dfn值low值
如果一節點滿足以下則為割點

  1. 下一點的 low值 大於等於此點的 dfn值
  2. root 有兩個 child 或不為 root

# 參考程式碼

#include <iostream>
#include <vector>
#include <string>
#include <sstream>
using namespace std;
vector< vector<int> > edge;
vector<int> dfn, low;
int result, dep;
void dfs(int cur, int par)
{
	bool cut = false;
	int child = 0;
	dfn[cur] = low[cur] = ++dep;
	for (auto& i : edge[cur]) {
		if (!dfn[i]) {
			++child;
			dfs(i, cur);
			low[cur] = min(low[cur], low[i]);
			if (low[i] >= dfn[cur]) cut = true;
		}
		else if (i != par) low[cur] = min(low[cur], dfn[i]);
	}
	if ((child >= 2 || par != -1) && cut) ++result;
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	int N;	
	while (cin >> N && N) {
		cin.ignore();
		result = 0, dep = 0;
		edge.assign(N + 1, vector<int>());
		dfn.assign(N + 1, 0);
		low.assign(N + 1, 0);
		string str;
		while (getline(cin, str)) {
			stringstream ss(str);
			int u, v;
			
			ss >> u;
			if (!u) break;
			while (ss >> v) edge[v].emplace_back(u), edge[u].emplace_back(v);
		}
		dfs(1, -1);
		cout << result << "\n";
	}
	return 0;
}

# 參考資料

https://www.larrysprognotes.com/UVa%20-%20315/