# 題目: UVa 315 - Network

# 題目說明

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

割點定義:

---

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/