# 題目: UVa 796 - Critical Links

# 題目說明

給一個無向圖，求bridge的數量及bridge為哪兩個點連接

bridge定義:

---

INPUT:
每筆測資第一行有一個整數N，代表有N個節點(0 ~ N-1)
接下來有N行，每行第一個數字為該點，括號刮起來為連到的節點數
例如2 (2) 1 3代表有兩個邊(2, 1)、(2, 3)

---

OUTPUT:
輸出bridge的數量及bridge為哪兩個點連接

# 解題方法

先建圖
之後跑dfs，由於此圖不一定連通，所以最多跑N次
之後跑dfs，紀錄每個點的dfn值及low值
如果下一點的low值大於此點的dfn值，則這兩個點間存在一條bridge

# 參考程式碼

#include <iostream>
#include <vector>
#include <queue>
#define p pair<int, int>

using namespace std;

vector< vector<int> > graph;
vector<int> dfn, low;
priority_queue<p, vector<p>, greater<p>> result;
int dep;

void dfs(int cur, int par)
{
	dfn[cur] = low[cur] = ++dep;

	for (auto& i : graph[cur]) {

		if (!dfn[i]) {
			dfs(i, cur);
			low[cur] = min(low[cur], low[i]);
		}
		else if (i != par) low[cur] = min(low[cur], dfn[i]);

		p tmp = { min(i, cur), max(i, cur) };
		if (low[i] > dfn[cur]) result.emplace(tmp);
	}
}

int main()
{
	int N;

	while (cin >> N) {

		graph.assign(N, vector<int>());
		dfn.assign(N, 0);
		low.assign(N, 0);
		dep = 0;

		for (int i = 0, a, b, n; i < N; ++i) {

			char tmp;
			cin >> a >> tmp >> n >> tmp;
			while (n--) cin >> b, graph[a].emplace_back(b);
		}

		for (int i = 0; i < N; ++i) if (!dfn[i]) dfs(i, -1);

		cout << result.size() << " critical links\n";
		while (!result.empty()) {
			cout << result.top().first << " - " << result.top().second << "\n";
			result.pop();
		}
		cout << "\n";
	}

	return 0;
}

# 參考資料

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