題目： UVa - 1108 - Mining Your Own Business

題目說明

給一個連通的無向圖，求最少在圖上標記幾個點，使得圖上任意一點崩塌 ( 被拿掉 ) 後，其他所有的點都能夠走到被標記的點。

Input： 每組測資起始於一整數 N，若 N 為 0 代表結束，否則下面 N 行，每行會有兩個整數 u、v，表示圖上有邊 (u, v)。

Output： 輸出最少需要標記的點及標記點的方法數。

解題思路

解這道題首先需要求出 Binconnected component ( 以下簡稱為 BCC )，因為在 BCC 上拿掉任意一點都不會打破原本的連通性 ( 因為 BCC 上沒有割點 )，之後我們可以發現，因為原本圖是連通的，所以我們只需要在 只有連接到另一個 BCC 的 BCC 上有標記點即可，因為若一個 BCC 連接到兩個以上的 BCC，則在整張圖上拿掉任意一點，在這個 BCC 上的點都可以走到其他的 BCC 上被標記的點。我們也可以發現，雖然標記在割點上能使得連接到的 BCC 都能走到，能夠達到標記最少的點，但是若被拿掉的是割點則會打破原本連通性的導致連接到的 BCC 都不能走到被標記的點，所以不能標記在割點上。

這道題需使用兩次 DFS ( 一次或許可以，但我不會 )，為了方便理解，將解法分成以下幾個步驟。

  1. 讀取測資並建圖，記得建雙向，因為是無向圖。

  2. 在圖上進行一次 DFS，根據割點的定義找出所有割點。

  3. 再進行一次 DFS，找出所有 BCC 連接的割點數量 ( 即表示 BCC 連接到其他 BCC 的數量 )，若只有 1 則將此 BCC 的節點數保存。

  4. 最後的方法數即為第三步所有保存的 BCC 的節點數相乘 ( 在每個 BCC 上選任意一點標記 )，標記點的數量即為保存的 BCC 的個數。

需要注意的是，若整張圖就是一個 BCC，則只需要在上面任意標記兩點，方法數則為 n * (n - 1) / 2， n 為點的數量。

方法數需使用 long long 運算及保存

參考解法

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
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
#include <iostream>
#include <algorithm>
#include <unordered_set>
#include <vector>
#include <map>

using namespace std;

/*
reference:
題目: https://ppt.cc/fkzEYx
解題想法: https://ppt.cc/fbXXcx
雙連通分量: https://ppt.cc/fs5cxx
Code: https://ppt.cc/fsPeKx
*/

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

int TIME;
int comSize;               // 目前遍歷的 Biconnected component 的節點數
map<int, int> dfn;
map<int, int> low;
map<int, vector<int>> G;
unordered_set<int> isCut;  // 儲存所有割點
unordered_set<int> visited;
unordered_set<int> adjCut; // 一個 Biconnected component 連接到的割點

void 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]);

        // 記錄所有割點
        if (low[v] >= dfn[u] && (child >= 2 || parent != -1)) isCut.insert(u);
    }
}

void findAns(int u)
{
    visited.insert(u);
    ++comSize;

    for (auto& v : G[u])
    {
        if (visited.count(v) || isCut.count(v))
        {
            // 如果 v 是割點
            if (isCut.count(v)) adjCut.insert(v);
            continue;
        }

        findAns(v);
    }
}

int main()
{
    int N, Case = 0;

    while (cin >> N && N)
    {
        // init
        TIME = 0;
        dfn.clear();
        low.clear();
        G.clear();
        isCut.clear();
        visited.clear();

        // build the graph
        for (int i = 0; i < N; ++i)
        {
            int u, v;
            cin >> u >> v;

            G[u].push_back(v);
            G[v].push_back(u);
        }

        // 尋找所有割點
        for (auto& [u, __] : G) if (!dfn[u]) dfs(u, -1);

        vector<int> D; // 儲存每個 Biconnected component 的節點數量
        for (auto& [u, __] : G)
        {
            if (visited.count(u) || isCut.count(u)) continue;

            comSize = 0;
            adjCut.clear();
            findAns(u);

            // 如果遍歷到的 Biconnected component 只連接到一個割點才需要有標記點
            if (adjCut.size() == 1) D.push_back(comSize);
        }

        // Biconnected component 的個數代表最少需要有幾個標記點 ( 個數不為 1 的情況 )
        long long ways = 1, mn = D.size();
        for (auto& i : D) ways *= i;

        // 如果整個圖本身為一個 Biconnected component，則任選兩點標記，mn 為 2
        if (D.empty()) ways = (long long)G.size() * (G.size() - 1) / 2, mn = 2;

        cout << "Case " << ++Case << ": " << mn << " " << ways << '\n';
    }
}

參考資料

Mining Your Own Business - 洛谷
UVA 1108 Mining Your Own Business ( 點雙連通分量 ) - 0w1
(Template) Connected component
UVa 1108 - Mining Your Own Business | Morris’ Blog