題目： UVa - 315 - Network

題目說明

給一個所有點都有接通的無向圖，找出 Articulation Points ( 也叫 Cut Vertex、割點 ) 的數量。

Articulation Points 的定義：

  1. 對於根節點 root，若其有兩棵或兩棵以上的子樹 ( degree >= 2 )，則該根節點 root 為割點。
  2. 對於非葉子節點 u ( 非根節點 )，若其 child 存在一個節點 v 或 v 的 descendant 沒有指向 u 的 proper ancestor ( 不包含 u ) 的 Back edge，則節點 u 為割點。

Input： 每組測資的第一行為一整數 N，表示有 N 個節點，若 N 為 0 代表結束，接下來最多 N 行為以空格隔開的數字，若為 0 則代表這筆測資結束，否則代表邊。如 5 1 2 3 4 表示有 ( 5, 1 )、( 5, 2 )、( 5, 3 )、( 5, 4 ) 這些邊。

Output： 輸出 Articulation Points 的數量。

解題思路

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

參考解法

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
82
83
84
85
86
87
88
89
90
91
92
93
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <sstream>
#include <functional>

using namespace std;

/* reference:
https://ppt.cc/fuwZGx
https://ppt.cc/fUny8x
*/

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

int main()
{
    int N; // 點的數量
    int time; // dfs 的順序
    int ret;
    string str;
    stringstream ss;
    vector<vector<int>> G;
    vector<int> dfsD;
    vector<int> low;

    // parent 為 0 表示 n 為 root
    function<void(int, int)> dfs = [&](int n, int parent)
    {
        int child = 0;
        bool flag = false;

        dfsD[n] = low[n] = ++time;

        for (auto& i : G[n])
        {
            // 如果不為 0 表示遍歷過了
            if (dfsD[i])
            {   // 若 i 不為 n 的 parent 才能更新 low 值
                if (parent != i) low[n] = min(dfsD[i], low[n]);
                continue;
            }
            
            ++child;
            dfs(i, n);
            low[n] = min(low[i], low[n]);

            if (low[i] >= dfsD[n]) flag = true;
        }

        // 如果 n 為根節點，則 child >= 2 就是割點
        // 否則只要 n 存在一個的 child，i 或 i 的 descendant 沒有 backedge ( 即 low[i] >= dfsD[n] ) 則 n 為割點
        if (flag && (child >= 2 || parent)) ++ret;
    };

    while (cin >> N && N)
    {
        cin.ignore();

        // init
        G.assign(N + 1, vector<int>());
        dfsD.assign(N + 1, 0);
        low.assign(N + 1, 0);
        time = 0;
        ret = 0;

        // 題目說最多 N 行，本來用 for 0 ~ N - 1 不知道為什麼會 WA，換成 0 ~ N 又會對，所以直接換成這樣
        while (getline(cin, str) && str != "0")
        {
            ss.clear();
            ss.str(str);

            int a, b;
            ss >> a;
            while (ss >> b)
            {   // 因為是無向圖，所以雙向都要建邊
                G[a].push_back(b);
                G[b].push_back(a);
            }
        }

        dfs(1, 0);
        
        cout << ret << '\n';
    }
}

參考資料

UVa 315 & POJ 1144 Network
圖論（二）：圖的割點(cut vertex)與連通度(connectivity)