# 題目: UVa 796 - Critical Links
# 題目說明
給一個無向圖,求 bridge
的數量及 bridge
為哪兩個點連接
bridge 定義:
- 一個連通圖,若拿掉一個邊會使此圖不連通,則此邊為
bridge
- 對於任意邊,一點不存在連通至
ancester
的backedge
,則此邊為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/