(Template) Connected component

Posted on | In , ,

BCC and SCC，使用 Tarjan 來求取。

BCC

一張無向圖上，不會產生關節點 (articulation point) 的連通分量，稱作「雙連通分量」(Biconnected Component)。

一張無向圖上，不會產生橋 (bridge) 的連通分量，稱作「橋連通分量」(Bridge-connected Component)。

Bridge-connected Component 模板

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
const int MAX_N = 5555;
vector<int> g[MAX_N];
int tt, dfn[MAX_N], low[MAX_N];
int bcc;
int belong[MAX_N]; // 縮點用
stack<int> s;
void dfs(int u, int p)
{
    dfn[u] = low[u] = tt++;
    s.push(u);
    for (int i = 0; i < (int)g[u].size(); i++) {
        int v = g[u][i];
        if (v == p)
            continue;
        if (dfn[v] == -1) {
            dfs(v, u);
            low[u] = min(low[u], low[v]);
        } else {
            low[u] = min(low[u], dfn[v]);
        }
    }
    if (low[u] == dfn[u]) {
        bcc++;
        while (1) {
            int v = s.top();
            s.pop();
            belong[v] = bcc;
            if (v == u)
                break;
        }
    }
}

Biconnected Component 模板

stack 塞入邊而不是塞入點，這樣就可以在找到 articulation point 時，得到每個團的資訊。

驗證：POJ 3177 Redundant Paths

求取 BCC 後縮點。縮點後最遠的兩葉子相連可以形成一個環，這需要做 (left + 1) / 2次。可以參考照篇文章來思考。

注意重邊。

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
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <stack>
#include <vector>
using namespace std;
const int MAX_N = 5555;
vector<int> g[MAX_N];
int tt, dfn[MAX_N], low[MAX_N];
int bcc;
int belong[MAX_N];
stack<int> s;
bool seen[MAX_N][MAX_N];
void dfs(int u, int p)
{
    dfn[u] = low[u] = tt++;
    s.push(u);
    for (int i = 0; i < (int)g[u].size(); i++) {
        int v = g[u][i];
        if (v == p)
            continue;
        if (dfn[v] == -1) {
            dfs(v, u);
            low[u] = min(low[u], low[v]);
        } else {
            low[u] = min(low[u], dfn[v]);
        }
    }
    if (low[u] == dfn[u]) {
        bcc++;
        while (1) {
            int v = s.top();
            s.pop();
            belong[v] = bcc;
            if (v == u)
                break;
        }
    }
}
int main()
{
    int n, m;
    scanf("%d %d", &n, &m);
    // memset(seen, 0, sizeof(seen)); // memset will cause MLE
    for (int i = 0; i < m; i++) {
        int u, v;
        scanf("%d %d", &u, &v);
        if (seen[u][v])
            continue;
        seen[u][v] = seen[v][u] = true;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    memset(dfn, -1, sizeof(dfn));
    memset(low, -1, sizeof(low));
    memset(belong, 0, sizeof(belong));
    bcc = 0;
    tt = 0;
    for (int i = 1; i <= n; i++)
        if (dfn[i] == -1) {
            dfs(i, -1);
        }
    int degree[MAX_N];
    memset(degree, 0, sizeof(degree));
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j < (int)g[i].size(); j++) {
            int v = g[i][j];
            if (belong[i] != belong[v]) {
                degree[belong[v]]++;
                degree[belong[i]]++;
            }
        }
    }
    int ans = 0;
    for (int i = 1; i <= n; i++) {
        if (degree[i] == 2)
            ans++;
    }
    printf("%d\n", (ans + 1) / 2);
    return 0;
}

SCC

模板

in_stack 檢查可以用下圖思考。

$$
A \rightarrow B \
C \rightarrow B \
D \rightarrow C
$$

如果今天走訪順序為 $B, A, D$，沒檢查 in_stack 的話，$C$ 的 low 會變成 $B$ 的，造成 $C$ 和 $D$ 在相同 SCC，但是這是錯誤的。

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
const int MAX_N = 11111;
vector<int> g[MAX_N];
int tt = 0, dfn[MAX_N], low[MAX_N];
stack<int> s;
int belong[MAX_N];
bool in_stack[MAX_N];
int scc = 0;
void dfs(int u, int p)
{
    dfn[u] = low[u] = tt++;
    s.push(u);
    in_stack[u] = true;
    for (int i = 0; i < (int)g[u].size(); i++) {
        const int &v = g[u][i];
        if (dfn[v] == -1) {
            dfs(v, u);
            low[u] = min(low[u], low[v]);
        } else {
            if (in_stack[v])
                low[u] = min(low[u], dfn[v]);
        }
    }
    if (dfn[u] == low[u]) {
        scc++;
        while (1) {
            int v = s.top();
            s.pop();
            belong[v] = scc;
            in_stack[v] = false;
            if (u == v)
                break;
        }
    }
}

縮 SCC 點之後，如果只有一個 DAG，那 out degree 為零的那個點就會答案，因為大家都會到達那裡！詳細解釋請看這裏。

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
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <stack>
#include <vector>
using namespace std;
const int MAX_N = 11111;
vector<int> g[MAX_N];
int tt = 0, dfn[MAX_N], low[MAX_N];
stack<int> s;
int belong[MAX_N];
bool in_stack[MAX_N];
int scc = 0;
void dfs(int u, int p)
{
    dfn[u] = low[u] = tt++;
    s.push(u);
    in_stack[u] = true;
    for (int i = 0; i < (int)g[u].size(); i++) {
        const int &v = g[u][i];
        // if(v == p) // wrong condition, sample input can reveal this error
        // continue;
        if (dfn[v] == -1) {
            dfs(v, u);
            low[u] = min(low[u], low[v]);
        } else {
            if (in_stack[v])
                low[u] = min(low[u], dfn[v]);
        }
    }
    if (dfn[u] == low[u]) {
        scc++;
        while (1) {
            int v = s.top();
            s.pop();
            belong[v] = scc;
            in_stack[v] = false;
            if (u == v)
                break;
        }
    }
}
int main()
{
    int n, m;
    while (scanf("%d %d", &n, &m) == 2) {
        for (int i = 0; i < n; i++)
            g[i].clear();
        for (int i = 0; i < m; i++) {
            int u, v;
            scanf("%d %d", &u, &v);
            u--;
            v--;
            g[u].push_back(v);
        }
        tt = 0;
        scc = 0;
        memset(dfn, -1, sizeof(dfn));
        memset(low, -1, sizeof(low));
        memset(belong, 0, sizeof(belong));
        memset(in_stack, false, sizeof(in_stack));
        for (int i = 0; i < n; i++) {
            if (dfn[i] == -1) {
                dfs(i, -1);
            }
        }
        int inDeg[scc + 1], outDeg[scc + 1];
        memset(inDeg, 0, sizeof(inDeg));
        memset(outDeg, 0, sizeof(outDeg));
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < (int)g[i].size(); j++) {
                int u = i;
                int v = g[i][j];
                if (belong[u] != belong[v]) {
                    inDeg[belong[v]]++;
                    outDeg[belong[u]]++;
                }
            }
        }
        int cnt_no_out = 0, who;
        for (int i = 1; i <= scc; i++) { // 注意 scc 區間，別被弄混了
            if (outDeg[i] == 0) {
                cnt_no_out++;
                who = i;
            }
        }
        if (cnt_no_out != 1)
            printf("0\n");
        else {
            int ans = 0;
            for (int i = 0; i < n; i++)
                if (belong[i] == who)
                    ans++;
            printf("%d\n", ans);
        }
    }
    return 0;
}