題目： UVa - 796 - Critical Links

題目說明

給一個無向圖，求 Bridge 的數量 及 Bridge。

Bridge 的定義：

  1. 對於一個連通的無向圖來說，若拿掉某一邊會導致原本連通的圖變得不連通，則該邊為 Bridge。
  2. 對於任意邊 (u, v)，若 v 及 v 的 descendant 不存在一條連接到 u 的 ancestor 的 Back edge，則 (u, v) 為 Bridge。

Input： 每組測資的第一行為一整數 N，表示圖有幾個點 (0 ~ N - 1)，接下來 N 行為每個點的連接情況，第一個數字為該點，後面接一個用左右括號括起來的數字 n，表示連接到 n 個點，後面 n 個數字為連接到的點，中間都以空格隔開。

Output： 輸出 Bridge 的數量及 Bridge。Bridge 要求輸出時是小的點連接到大的點 ( 如 (1, 5) 需輸出為 "1 - 5"，不可輸出為 "5 - 1" )，並且先依照前面的數字小到大排序，若前面一樣則依照後面的數字小到大排序 ( 即為 pair 的比較方法 )。

解題思路

先讀取測資並建圖，之後 DFS，紀錄 DFS 時的序號及 low 值 ( 記錄節點 u 或 u 的子樹通過非父子邊追溯到最早的祖先節點 ( 即 DFS 的序號最小 ) )，之後根據 Bridge 的定義判斷並記錄即可。

註： 測資提供的是所有點的**所有連接情況**，如 1 和 5 相連，則在 1 的時候會出現 5 代表 1 連到 5，在 5 的時候也會出現 1 代表 5 連到 1。

參考解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
#include <iostream>
#include <algorithm>
#include <functional>
#include <vector>
#include <queue>

using namespace std;

// reference: https://ppt.cc/fzjSzx

static auto __ = []
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    return 0;
}();

int main()
{
    int N;
    int time;
    vector<vector<int>> G;
    vector<int> dfsD;
    vector<int> low;
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;

    // parent 為 -1 代表沒有 parent
    function<void(int, int)> dfs = [&](int n, int parent)
    {
        dfsD[n] = low[n] = ++time;

        for (auto& i : G[n])
        {
            if (dfsD[i])
            {
                if (parent != i) low[n] = min(dfsD[i], low[n]);
                continue;
            }

            dfs(i, n);
            low[n] = min(low[i], low[n]);

            // 如果 low[i] 大於 dfsD[n] 表示 i 及 i 的 descendant 沒有 backedge
            // 連接到 n 的 ancestor ( 包含 n )，則 ( u, v ) 為 bridge
            // 由於題目要求較小的放在前面，所以這樣存入
            if (low[i] > dfsD[n]) pq.push({ min(n, i), max(n, i) });
        }
    };

    while (cin >> N)
    {
        // init
        time = 0;
        G.assign(N, vector<int>());
        dfsD.assign(N, 0);
        low.assign(N, 0);
        // pq 每次結束後都會清空

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

            // 雖然是無向圖，但是測資給的是點的所有連接情況，如果這邊建雙向的話會造成重複
            // 如 (1, 5) 及 (5, 1) 所以這裡建單向即可，這樣建出來的圖最後即是雙向的
            while (n--) cin >> b, G[a].push_back(b);
        }

        for (int i = 0; i < N; ++i) if (!dfsD[i]) dfs(i, -1);
        
        cout << pq.size() << " critical links" << '\n';
        while (!pq.empty())
        {
            cout << pq.top().first << " - " << pq.top().second << '\n';
            pq.pop();
        }
        cout << '\n';
    }
}

參考資料

UVa 796 - Critical Links | NaiveRed’s Blog