【模板】边双连通分量

GitHub 跳转原题关系图返回列表

先用 Tarjan 找出无向图中的所有桥，再把这些桥删掉，剩下的每个连通块就是一个边双连通分量。

OJ: luogu

题目 ID: P8436

难度:提高+/省选-

标签:图论tarjan双连通分量边双

日期: 2026-06-20 01:49

题意

给一张允许有重边、自环，而且可能不连通的无向图。

要求输出：

边双连通分量的个数
每个边双连通分量里有哪些点

这里的边双连通分量可以理解成：

在这个点集内部，任意两点之间至少有两条边不重复的路径
或者等价地说，这个点集内部没有桥作为唯一通道

样例图

下面这张图用样例三来说明“桥把边双隔开”这件事：

graph G {
  1 -- 2;
  1 -- 3;
  2 -- 3;
  2 -- 4 [color=red, penwidth=2];
  4 -- 6 [color=red, penwidth=2];
  5;
}

图中红色边 2-4 和 4-6 都是桥。把它们删掉以后，图就被分成了四块：

{1,2,3}
{4}
{5}
{6}

这四个连通块，正好就是这个样例的边双连通分量。

思路

先看一个可以直接验证想法的小数据暴力：

cpp

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// brute.cpp：小数据暴力。
// 先枚举每条边判断它是不是桥，再删掉所有桥求连通块，这些连通块就是边双连通分量。
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 20;
const int MAXM = 40;
const int MAXE = MAXM * 2 + 5;

struct Edge {
    int u, v;
} edges[MAXM];

int n, m;
int head[MAXN], to[MAXE], nxt[MAXE], edge_cnt;
bool vis[MAXN];
bool is_bridge[MAXM];
vector< vector<int> > answer;

void init_graph() {
    edge_cnt = 0;
    for (int i = 1; i <= n; i++) {
        head[i] = -1;
        vis[i] = false;
    }
}

void add_edge(int u, int v) {
    to[edge_cnt] = v;
    nxt[edge_cnt] = head[u];
    head[u] = edge_cnt;
    edge_cnt++;
}

void build_graph(int ban_edge, bool remove_bridges) {
    init_graph();
    for (int i = 1; i <= m; i++) {
        if (i == ban_edge) {
            continue;
        }
        if (remove_bridges && is_bridge[i]) {
            continue;
        }
        add_edge(edges[i].u, edges[i].v);
        add_edge(edges[i].v, edges[i].u);
    }
}

void dfs_count(int u) {
    vis[u] = true;
    for (int i = head[u]; i != -1; i = nxt[i]) {
        int v = to[i];
        if (!vis[v]) {
            dfs_count(v);
        }
    }
}

int count_components(int ban_edge) {
    build_graph(ban_edge, false);

    int cnt = 0;
    for (int i = 1; i <= n; i++) {
        if (!vis[i]) {
            cnt++;
            dfs_count(i);
        }
    }
    return cnt;
}

void dfs_collect(int u, vector<int> &comp) {
    vis[u] = true;
    comp.push_back(u);

    for (int i = head[u]; i != -1; i = nxt[i]) {
        int v = to[i];
        if (!vis[v]) {
            dfs_collect(v, comp);
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        cin >> edges[i].u >> edges[i].v;
        is_bridge[i] = false;
    }

    int base_cc = count_components(0);
    for (int i = 1; i <= m; i++) {
        int cc = count_components(i);
        if (cc > base_cc) {
            is_bridge[i] = true;
        }
    }

    build_graph(0, true);
    for (int i = 1; i <= n; i++) {
        if (!vis[i]) {
            vector<int> comp;
            dfs_collect(i, comp);
            answer.push_back(comp);
        }
    }

    cout << answer.size() << '\n';
    for (size_t i = 0; i < answer.size(); i++) {
        cout << answer[i].size();
        for (size_t j = 0; j < answer[i].size(); j++) {
            cout << ' ' << answer[i][j];
        }
        cout << '\n';
    }

    return 0;
}

暴力做法分两步：

枚举每一条边，删掉它后重新数连通块个数
如果连通块数量变多，说明它是桥
把所有桥都删掉，再做一次 DFS，剩下的每个连通块就是一个边双

这个过程很好理解，但每条边都重新搜一遍图，复杂度太高，只适合小数据。

正式做法沿用你书里的那条主线：

桥是边双之间的边界
去掉所有桥以后，每个连通块就是一个边双

所以我们只要先用 Tarjan 找桥，再忽略桥做第二遍 DFS 即可。

对 DFS 树上的一条树边 u -> v，如果满足：

low[v] > dfn[u]

说明 v 这棵子树没法绕回 u 或 u 的祖先，那么边 u-v 就是桥。

这题还有两个实现细节需要特别注意：

图里可能有重边，不能只靠 v != fa 来跳过父边，必须记录“进入当前点的是哪条边”，遍历时只跳过它的反向边
数据范围到 5e5 个点、2e6 条边，递归 DFS 很容易爆栈，所以代码里改成了非递归 Tarjan 和非递归 DFS

最后第二遍遍历时，所有桥边都直接跳过。这样搜到的一整块点，就是同一个边双连通分量。

代码

cpp

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
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182#include <bits/stdc++.h>
using namespace std;

const int MAXN = 500000 + 5;
const int MAXM = 4000000 + 5;

int n, m;

// 链式前向星存图，边编号从 0 开始，方便用 i ^ 1 找反向边。
int head[MAXN], to[MAXM], nxt[MAXM], edge_cnt;

// Tarjan 找桥需要的时间戳数组。
int dfn[MAXN], low[MAXN], dfs_clock;
bool is_bridge[MAXM];

// 非递归 DFS 需要记录当前处理到哪一条边。
int iter_edge[MAXN];
int parent_node[MAXN], parent_edge[MAXN];

// 第二遍忽略桥做 DFS 染色。
bool vis[MAXN];
int comp_iter[MAXN];

vector< vector<int> > answer;

void init_graph(int n) {
    edge_cnt = 0;
    dfs_clock = 0;
    answer.clear();

    for (int i = 1; i <= n; i++) {
        head[i] = -1;
        dfn[i] = 0;
        low[i] = 0;
        vis[i] = false;
    }
}

void add_edge(int u, int v) {
    to[edge_cnt] = v;
    nxt[edge_cnt] = head[u];
    head[u] = edge_cnt;
    edge_cnt++;
}

// 非递归 Tarjan：先找出所有桥。
void tarjan_bridge() {
    vector<int> st;
    st.reserve(n);

    for (int start = 1; start <= n; start++) {
        if (dfn[start]) {
            continue;
        }

        parent_node[start] = 0;
        parent_edge[start] = -1;
        st.push_back(start);

        while (!st.empty()) {
            int u = st.back();

            if (!dfn[u]) {
                dfn[u] = low[u] = ++dfs_clock;
                iter_edge[u] = head[u];
            }

            int &i = iter_edge[u];
            if (i != -1) {
                int e = i;
                i = nxt[i];
                int v = to[e];

                if (e == (parent_edge[u] ^ 1)) {
                    continue;
                }

                if (!dfn[v]) {
                    parent_node[v] = u;
                    parent_edge[v] = e;
                    st.push_back(v);
                    continue;
                }

                // 已访问点只在它是祖先时更新 low。
                if (dfn[v] < dfn[u]) {
                    low[u] = min(low[u], dfn[v]);
                }
                continue;
            }

            st.pop_back();
            if (parent_edge[u] != -1) {
                int p = parent_node[u];
                low[p] = min(low[p], low[u]);

                if (low[u] > dfn[p]) {
                    is_bridge[parent_edge[u]] = true;
                    is_bridge[parent_edge[u] ^ 1] = true;
                }
            }
        }
    }
}

// 第二遍 DFS：忽略所有桥，遍历顺序尽量保持和递归版一致。
void collect_component(int start) {
    vector<int> comp;
    vector<int> st;

    vis[start] = true;
    comp.push_back(start);
    comp_iter[start] = head[start];
    st.push_back(start);

    while (!st.empty()) {
        int u = st.back();
        int &i = comp_iter[u];
        bool advanced = false;

        while (i != -1) {
            int e = i;
            i = nxt[i];
            int v = to[e];

            if (is_bridge[e] || vis[v]) {
                continue;
            }

            vis[v] = true;
            comp.push_back(v);
            comp_iter[v] = head[v];
            st.push_back(v);
            advanced = true;
            break;
        }

        if (!advanced && i == -1) {
            st.pop_back();
        }
    }

    answer.push_back(comp);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m;
    init_graph(n);

    for (int i = 0; i < 2 * m; i++) {
        is_bridge[i] = false;
    }

    for (int i = 1; i <= m; i++) {
        int u, v;
        cin >> u >> v;
        add_edge(u, v);
        add_edge(v, u);
    }

    tarjan_bridge();

    for (int i = 1; i <= n; i++) {
        if (!vis[i]) {
            collect_component(i);
        }
    }

    cout << answer.size() << '\n';
    for (size_t i = 0; i < answer.size(); i++) {
        cout << answer[i].size();
        for (size_t j = 0; j < answer[i].size(); j++) {
            cout << ' ' << answer[i][j];
        }
        cout << '\n';
    }

    return 0;
}

复杂度

设点数为 n，边数为 m。

Tarjan 找桥一遍 $O(n+m)$ ，删桥后再搜连通块也是一遍 $O(n+m)$ ，所以：

时间复杂度 $O(n+m)$
空间复杂度 $O(n+m)$

总结

这题最核心的一句话就是：

桥把不同边双隔开

因此“求边双”可以转成：

先求所有桥
再把桥删掉
剩下每个连通块就是答案

理解了这件事，后面的边双缩点、桥树等题都会顺很多。

一图流解析

这张图把本题的建模、关键转移、实现检查和训练方法压缩到一页，适合读完正文后复盘。

P8436 【模板】边双连通分量

题目描述

对于一个 $n$ 个节点 $m$ 条无向边的图，请输出其边双连通分量的个数，并且输出每个边双连通分量。

输入格式

第一行，两个整数 $n$ 和 $m$ 。

接下来 $m$ 行，每行两个整数 $u, v$ ，表示一条无向边。

不保证图为简单图，图中可能有重边和自环。

输出格式

第一行一个整数 $x$ 表示边双连通分量的个数。

接下来的 $x$ 行，每行第一个数 $a$ 表示该分量结点个数，然后 $a$ 个数，描述一个边双连通分量。

你可以以任意顺序输出边双连通分量与边双连通分量内的结点。

输入输出样例 #1

输入 #1

text

输出 #1

text

1
21
5 1 5 4 2 3

输入输出样例 #2

输入 #2

text

输出 #2

text

输入输出样例 #3

输入 #3

text

输出 #3

text

输入输出样例 #4

输入 #4

text

输出 #4

text

1
2
3
43
1 1
5 2 5 3 6 4
1 7

说明/提示

样例四解释：

相同颜色的点为同一个连通分量。

数据范围： 对于 $100\%$ 的数据， $1 \le n \le 5 \times10 ^5$ ， $1 \le m \le 2 \times 10^6$ 。

subtask	$n$	$m$	分值
$1$	$1 \le n \le 100$	$1 \le m \le 500$	$25$
$2$	$1 \le n \le 5000$	$1 \le m \le 5 \times 10^4$	$25$
$3$	$1 \le n \le 2\times 10^5$	$1 \le m \le 5\times 10^5$	$25$
$4$	$1 \le n \le 5 \times10 ^5$	$1 \le m \le 2 \times 10^6$	$25$

数据更新

$2022/7/14$ 加强数据
$2022/11/26$ 新增 $10$ 组较小的数据（ $1\le n, m \le 10$ )，方便选手调试。
$2022/12/31$ 重组 $subtask$ ，并加入若干组极端数据。
$2023/1/1$ 发现昨天新加入的数据数据出了问题，已修改。

本题不卡常，时间限制与空间限制均已开大，正确的解法均可通过。

惊喜：AC 后记得把鼠标放到测试点上看反馈信息，有惊喜哦。

【模板】边双连通分量

目录

题意

样例图

思路

代码

复杂度

总结

一图流解析