连通性问题

Hervey Lv3
  2024-02-08 07:31:54 2024-02-08 07:31:54 创建   2025-03-02 14:22:27 2025-03-02 14:22:27 更新      

0 前言

总结一些连通性问题的常用模板 (Tarjan的变形好多QwQ)

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
#include <bits/stdc++.h>

using namespace std;

const int N = 150 + 5;
const int M = 5000 + 5;

int head[N], nxt[M << 1], to[M << 1], tot;
inline void addedge(int u, int v)
{
    nxt[tot] = head[u];
    to[tot] = v;
    head[u] = tot++;
}

int edcc_num, edcc[N];
vector<pair<int, int>> cutEdge;
int dfn[N], low[N], Index;
stack<int> S;
void Tarjan(int u, int lst)
{
    dfn[u] = low[u] = ++Index;
    S.push(u);
    for (int i = head[u]; i != -1; i = nxt[i])
    {
        if (i == (lst ^ 1))
            continue;
        int v = to[i];
        if (!dfn[v])
        {
            Tarjan(v, i);
            low[u] = min(low[u], low[v]);
            if (low[v] > dfn[u])
                cutEdge.push_back(make_pair(min(u, v), max(u, v)));
        }
        else
            low[u] = min(low[u], dfn[v]);
    }
    if (low[u] == dfn[u])
    {
        ++edcc_num;
        int v = -1;
        do
        {
            v = S.top();
            S.pop();
            edcc[v] = edcc_num;
        } while (u != v);
    }
}

int n, m;

int main()
{
    memset(head, -1, sizeof(head));
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= m; i++)
    {
        int u, v;
        scanf("%d%d", &u, &v);
        addedge(u, v);
        addedge(v, u);
    }
    for (int u = 1; u <= n; u++)
        if (!dfn[u])
            Tarjan(u, -1);
    sort(cutEdge.begin(), cutEdge.end());
    for (auto E : cutEdge)
        printf("%d %d\n", E.first, E.second);
    return 0;
}

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
#include <bits/stdc++.h>

using namespace std;

const int N = 3e5 + 5;
const int M = 3e5 + 5;

int head[N], nxt[M << 1], to[M << 1], tot;
inline void addedge(int u, int v)
{
    nxt[tot] = head[u];
    to[tot] = v;
    head[u] = tot++;
}

int vdcc_num, deg[N];
vector<int> vdcc[N], cutPoint;
int dfn[N], low[N], Index;
stack<int> S;
void Tarjan(int u, int lst)
{
    dfn[u] = low[u] = ++Index;
    S.push(u);
    for (int i = head[u]; i != -1; i = nxt[i])
    {
        if (i == (lst ^ 1))
            continue;
        int v = to[i];
        if (!dfn[v])
        {
            Tarjan(v, i);
            low[u] = min(low[u], low[v]);
            if (low[v] >= dfn[u])
            {
                ++vdcc_num;
                vdcc[vdcc_num].push_back(u);
                ++deg[u];
                int w = -1;
                do
                {
                    w = S.top();
                    S.pop();
                    vdcc[vdcc_num].push_back(w);
                    ++deg[w];
                } while (v != w);
            }
        }
        else
            low[u] = min(low[u], dfn[v]);
    }
}

int n, m;

int main()
{
    memset(head, -1, sizeof(head));
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= m; i++)
    {
        int u, v;
        scanf("%d%d", &u, &v);
        addedge(u, v);
        addedge(v, u);
    }
    for (int u = 1; u <= n; u++)
        if (!dfn[u])
        {
            while (!S.empty())
                S.pop();
            Tarjan(u, -1);
        }
    for (int u = 1; u <= n; u++)
        if (deg[u] > 1)
            cutPoint.push_back(u);
    printf("%d\n", cutPoint.size());
    for (int u : cutPoint)
        printf("%d ", u);
    return 0;
}

3 圆方树

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
#include <bits/stdc++.h>

using namespace std;

const int N = 3e5 + 5;
const int M = 3e5 + 5;

int head[N], nxt[M << 1], to[M << 1], tot;
inline void addedge(int u, int v)
{
    nxt[tot] = head[u];
    to[tot] = v;
    head[u] = tot++;
}

int idx;
vector<int> E[N];

int dfn[N], low[N], Index;
stack<int> S;
void Tarjan(int u)
{
    dfn[u] = low[u] = ++Index;
    S.push(u);
    for (int i = head[u]; i != -1; i = nxt[i])
    {
        int v = to[i];
        if (!dfn[v])
        {
            Tarjan(v);
            low[u] = min(low[u], low[v]);
            if (low[v] >= dfn[u])
            {
                ++idx;
                E[idx].push_back(u);
                E[u].push_back(idx);
                int w = -1;
                do
                {
                    w = S.top();
                    S.pop();
                    E[idx].push_back(w);
                    E[w].push_back(idx);
                } while (v != w);
            }
        }
        else
            low[u] = min(low[u], dfn[v]);
    }
}

int n, m;

int main()
{
    memset(head, -1, sizeof(head));
    scanf("%d%d", &n, &m);
    idx = n;
    for (int i = 1; i <= m; i++)
    {
        int u, v;
        scanf("%d%d", &u, &v);
        addedge(u, v);
        addedge(v, u);
    }
    for (int u = 1; u <= n; u++)
        if (!dfn[u])
        {
            while (!S.empty())
                S.pop();
            Tarjan(u);
        }
    return 0;
}

4 强连通分量

Kosaraju 算法

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
#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 5;

vector<int> E[N], rE[N];

bool vis[N];
stack<int> S;

void dfs1(int u)
{
    vis[u] = true;
    for (int v : E[u])
        if (!vis[v])
            dfs1(v);
    S.push(u);
}

int scc_num;
int siz[N], scc[N];
void dfs2(int u)
{
    vis[u] = true;
    scc[u] = scc_num;
    ++siz[scc_num];
    for (int v : rE[u])
        if (!vis[v])
            dfs2(v);
}

int n, m;

int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= m; i++)
    {
        int u, v;
        scanf("%d%d", &u, &v);
        E[u].push_back(v);
        rE[v].push_back(u);
    }
    for (int u = 1; u <= n; u++)
        if (!vis[u])
            dfs1(u);
    memset(vis, false, sizeof(vis));
    scc_num = 0;
    while (!S.empty())
    {
        ++scc_num;
        int u = S.top();
        S.pop();
        if (!vis[u])
            dfs2(u);
    }
    int ans = 0;
    for (int i = 1; i <= scc_num; i++)
        ans += siz[i] > 1;
    printf("%d\n", ans);
    return 0;
}

Tarjan 算法

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
#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 5;
const int M = 5e4 + 5;

int head[N], nxt[M], to[M], tot;
inline void addedge(int u, int v)
{
    nxt[tot] = head[u];
    to[tot] = v;
    head[u] = tot++;
}

int dfn[N], low[N], Index;
bool instack[N];
stack<int> S;
int scc_num, scc[N], siz[N];
void Tarjan(int u)
{
    low[u] = dfn[u] = ++Index;
    instack[u] = true;
    S.push(u);
    for (int i = head[u]; i != -1; i = nxt[i])
    {
        int v = to[i];
        if (!dfn[v])
        {
            Tarjan(v);
            low[u] = min(low[u], low[v]);
        } else if (instack[v])
            low[u] = min(low[u], dfn[v]);
    }
    if (low[u] == dfn[u])
    {
        ++scc_num;
        int v = -1;
        do
        {
            v = S.top();
            S.pop();
            instack[v] = false;
            scc[v] = scc_num;
            ++siz[scc_num];
        } while (u != v);
        
    }
}

int n, m;

int main()
{
    memset(head, -1, sizeof(head));
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= m; i++)
    {
        int u, v;
        scanf("%d%d", &u, &v);
        addedge(u, v);
    }
    for (int u = 1; u <= n; u++)
        if (!dfn[u])
            Tarjan(u);
    int ans = 0;
    for (int i = 1; i <= scc_num; i++)
        ans += siz[i] > 1;
    printf("%d\n", ans);
    return 0;
}
  • 标题: 连通性问题
  • 作者: Hervey
  • 创建于 : 2024-02-08 07:31:54
  • 更新于 : 2025-03-02 14:22:27
  • 链接: https://herveyb3b4.github.io/2024/02/08/Alogrithm/Notes/Connectivity-Problem/
  • 版权声明: 本文章采用 CC BY-NC-SA 4.0 进行许可。
目录
连通性问题
  1. 0 前言
  2. 1 无向图的边双连通性
    1. 求割边/边双连通分量
  3. 2 无向图的点双连通性
    1. 求割点/点双连通分量
  4. 3 圆方树
  5. 4 强连通分量
    1. Kosaraju 算法
    2. Tarjan 算法