題目： UVa - 10765 - Doves and bombs

題目說明

其實我不是太懂題目的意思，就以我理解的想法大致敘述一下。

給一個圖，求在圖上任意拿掉一點使得原本該點所在的連通圖會被分為幾個連通圖 ( 意思為在一個連通圖上拿掉一點，使得該連通圖被分為幾個連通圖 )，輸出前面幾個拿掉會造成原本的連通圖被分為最多個連通圖的點及連通圖的數量。

Input： 每筆測資的第一行為兩整數 n、m，n 表示圖上有 n 個點 (0 ~ N - 1)，若 n 及 m 皆為 0 代表結束。接下來每行會有兩個整數 u、v 表示邊 (u, v) 是連通的，若 u、v 皆為 -1 代表結束。

Output： 輸出前 m 大的結果 ( 值較大的在上面，若值相等則序號較小的在上面 )。

解題思路

先讀取測資並建圖，之後 DFS，紀錄 DFS 時的序號及 low 值 ( 記錄節點 u 或 u 的子樹通過非父子邊追溯到最早的祖先節點 ( 即 DFS 的序號最小 ) )，之後根據割點的定義，紀錄每個點被多少個點視為割點最後再加一即為該點的值，因為若一個點被另一個點視為割點，則該點拿掉的話會導致原本的連通圖變為兩個連通圖，同理，若被 N 個點視為割點則拿掉該點的話會導致原本的連通圖變為 N + 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
82
83
84
85
86
87
88
#include <iostream>
#include <algorithm>
#include <vector>
#include <functional>

using namespace std;

/*
reference:
https://ppt.cc/foedPx
https://ppt.cc/fxMzyx
*/

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

int main()
{
    int n, m;
    int TIME;
    vector<int> dfn;
    vector<int> low;
    vector<int> cnt;
    vector<vector<int>> G;
    vector<pair<int, int>> ret;

    function<void(int, int)> dfs = [&](int u, int parent)
    {
        int child = 0;

        dfn[u] = low[u] = ++TIME;

        for (auto& v : G[u])
        {
            if (dfn[v])
            {
                if (v != parent) low[u] = min(dfn[v], low[u]);
                continue;
            }

            ++child;
            dfs(v, u);
            low[u] = min(low[v], low[u]);

            // 紀錄有幾個點將 u 視為割點
            if (low[v] >= dfn[u] && (child >= 2 || parent != -1)) ++cnt[u];
        }
    };

    while (cin >> n >> m && (n || m))
    {
        // init
        TIME = 0;
        dfn.assign(n, 0);
        low.assign(n, 0);
        cnt.assign(n, 0);
        G.assign(n, vector<int>());
        ret.clear();

        int u, v;
        while (cin >> u >> v && !(u == -1 && v == -1))
        {   // 無向圖，建雙向邊
            G[u].push_back(v);
            G[v].push_back(u);
        }

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

        // 最後要加一是因為若有一個節點將此點視為割點，則拿掉此點
        // 圖會被分為兩部分，若有 n 個，則為 n + 1
        for (int i = 0; i < n; ++i) ret.push_back({ i, cnt[i] + 1 });

        // 根據題目的要求排序 ( 值較大的在上面，若值相等則序號較小的在上面 )
        auto cmp = [](pair<int, int>& l, pair<int, int>& r)
        {
            return l.second != r.second ? l.second > r.second : l.first < r.first;
        };
        sort(begin(ret), end(ret), cmp);

        for (int i = 0; i < m; ++i) cout << ret[i].first << " " << ret[i].second << '\n';
        cout << '\n';
    }
}

參考資料

[UVA][關節點] 10765 - Doves and bombs＠Morris’ Blog｜PChome 個人新聞台
UVa 10765 | 程式隨筆