# 題目說明

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

bridge 定義:

  1. 一個連通圖,若拿掉一個邊會使此圖不連通,則此邊為 bridge
  2. 對於任意邊,一點不存在連通至 ancesterbackedge ,則此邊為 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/