題目： UVa - 10972 - RevolC FaeLoN

題目說明

給一個無向圖，現在要把圖轉換成有向圖，且邊可以任意定向 ( 即原本邊 (u, v)，可以變為 u -> v 或 v -> u )。求需要加幾條邊才能使得轉換後的圖形為強連通 ( 即在有向圖上任意選兩點 u、v，u 能夠走到 v 且 v 也能夠走到 u )。

Input： 每組測資的第一行為兩個整數 n、m，分別代表 點的數量、邊的數量，後面 m 行每行有兩個整數 u、v，表示圖上有邊 (u, v)。

Output： 輸出最少需要加幾條邊使得圖轉換成有向圖後會是強連通。

解題思路

我們可以發現，無向圖中的 Bridge Connected Component ( 以下簡稱 BCC，注意不是 Biconnected component )，在把邊任意定向後一定可以變成一個強連通分量，原因在於強連通分量其實類似於無向圖中的環，詳細說明可參考本篇文章：【RevolC FaeLoN Uva 10972】 - 大米饼 - 博客园。

所以可以得出圖上 BCC 內的點其實不影響我們求解的結論，因此我們把圖上的所有 BCC 各自視為一個點 ( 即縮點的概念 )，而原本的 Bridge 會將這些點連接起來，接下來我們要做的就是使這些點強連通，對於縮點後的所有葉子節點，我們需要 (N + 1) / 2 條邊才能連接起來，N 為葉子節點的數量，對於縮點後的孤立點 ( 因為題目的圖不保證連通，所以可能會產生沒有連接到其他 BCC 也沒有被其他 BCC 連入的 BCC )，則需要 M 條邊才能連接起來，M 為孤立點的數量。至於原因請參考本篇文章：【RevolC FaeLoN Uva 10972】 - 大米饼 - 博客园。

解法分為以下幾個步驟：

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

  2. DFS 找出 BCC 的數量，因為若整張圖本身就是一個 BCC 則不需要增加任何邊。

  3. 根據 DFS 算出的 low 值取得 BCC 的連接情況。

  4. 最後根據上面的方法算出需要增加的邊即可。

註： 根據 low 值判斷 BCC 的情況可能不是很正確，因為一個 BCC 內的所有節點的 low 值不一定全部一樣，但是在這個題目中不影響，因為一個被視為葉子節點的 BCC，若被視為兩個 BCC，則原本的 BCC 一定被誤認為的 BCC 所連接，因此葉子節點的數量不改變。
其實可以使用一個數組保存 BCC 的情況再求解應該會更好，不過現在有點懶，之後再寫吧。

參考解法

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
#include <iostream>
#include <algorithm>
#include <vector>
#include <map>

using namespace std;

/* reference:
想法: https://ppt.cc/fXERhx
Code: https://ppt.cc/fNsXNx
*/

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

int n, m;      // input
int TIME;
int bcnt;      // bridge connected component 的數量
int dfn[1001]; // dfs 時的序號
int low[1001]; // dfs 時的 low 值
vector<int> G[1001];

// 找出 bridge connected component
void dfs(int u, int parent)
{
    dfn[u] = low[u] = ++TIME;

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

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

        // 找到一個橋，bridge connected component 的數量加一
        if (low[v] > dfn[u]) ++bcnt;
    }
}

void solve()
{
    // 如果整張圖本身就是一個 bridge connected component ( 沒有橋 )，則不需要新增邊
    if (bcnt == 1) { cout << 0 << '\n'; return; }

    // 每一組 bridge connected component 連接到的 bridge connected component 數量 -> degree
    map<int, int> m;
    for (int u = 1; u <= n; ++u)
    {
        m[low[u]] += 0; // 單獨一個 bridge connected component -> degree = 0
        for (auto& v : G[u]) if (low[v] != low[u]) ++m[low[u]];
    }

    int alone = 0, leaves = 0;
    for (auto& [__, de] : m)
    {
        if (!de) ++alone;
        else if (de == 1) ++leaves;
    }

    cout << alone + (leaves + 1) / 2 << '\n';
}

int main()
{
    while (cin >> n >> m)
    {
        // init
        TIME = 0;
        bcnt = 0;
        fill(dfn, dfn + 1001, 0);
        fill(low, low + 1001, 0);
        fill(G, G + 1001, vector<int>());

        while (m--)
        {
            int u, v;
            cin >> u >> v;
            G[u].push_back(v);
            G[v].push_back(u);
        }

        // 找出 bridge connected component 的數量
        for (int i = 1; i <= n; ++i)
        {
            if (!dfn[i])
            {
                dfs(i, -1);

                // 對於一個連通圖來說，若沒有橋則本身是 bridge connected component
                // 否則若圖中有一個橋，則圖會被分為兩個 bridge connected component
                // 所以這邊需要加一
                ++bcnt;
            }
        }

        solve();
    }
}

參考資料

【RevolC FaeLoN Uva 10972】 - 大米饼 - 博客园
uva 10972 RevolC FaeLoN - Titanium - 博客园