【模板】点双连通分量

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

Tarjan 回溯时若树边 u-v 满足 low[v] >= dfn[u]，说明 v 子树必须经过 u 才能连到外部，此时把点栈弹到 v 再加上 u，就得到一个点双连通分量。

OJ: luogu

题目 ID: P8435

难度:提高+/省选-

标签:图论tarjan双连通分量割点

日期: 2026-06-20 02:01

题意

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

要求输出：

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

这题采用的定义是：

一个极大的“没有割点”的连通子图，就是一个点双连通分量

所以这题和 P3388 的关系非常直接：

割点会把图切成多个点双
同一个割点可能同时属于多个点双

样例图

下面用样例三说明“割点把点双切开”：

graph G {
  1 -- 2;
  1 -- 3;
  2 -- 3;
  2 -- 4;
  4 -- 6;
  5;
}

这张图里：

2 是割点，因为删掉它以后，4、6 那一支会和左边断开
4 也是割点，因为删掉它以后，点 6 会单独断开

所以图被切成四个点双：

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

思路

先看一个更直观的小数据教学版：

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// brute.cpp：更直观的递归 Tarjan 教学版。
// 它和正式做法的判定逻辑一样，但递归深度只适合小数据，
// 主要用来帮助理解点栈出栈过程，并辅助对拍。
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 20;
const int MAXM = 100;

int n, m;
int head[MAXN], to[MAXM], nxt[MAXM], edge_cnt;

int dfn[MAXN], low[MAXN], dfs_clock;
int parent_edge[MAXN];
bool is_cut[MAXN];

vector<int> node_stack;
vector<int> component_nodes;
vector< vector<int> > answer;
vector< vector<int> > deferred_answer;

void init_graph() {
    edge_cnt = 0;
    dfs_clock = 0;
    answer.clear();
    deferred_answer.clear();
    node_stack.clear();

    for (int i = 1; i <= n; i++) {
        head[i] = -1;
        dfn[i] = 0;
        low[i] = 0;
        parent_edge[i] = -1;
        is_cut[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 dfs(int u, int in_edge, int root) {
    dfn[u] = low[u] = ++dfs_clock;
    node_stack.push_back(u);
    component_nodes.push_back(u);

    int child_cnt = 0;

    for (int i = head[u]; i != -1; i = nxt[i]) {
        int v = to[i];

        if (i == (in_edge ^ 1)) {
            continue;
        }

        if (!dfn[v]) {
            child_cnt++;
            parent_edge[v] = i;
            dfs(v, i, root);

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

            if (low[v] >= dfn[u]) {
                if (u != root) {
                    is_cut[u] = true;
                }

                vector<int> bcc;
                while (true) {
                    int x = node_stack.back();
                    node_stack.pop_back();
                    bcc.push_back(x);
                    if (x == v) {
                        break;
                    }
                }
                bcc.push_back(u);
                answer.push_back(bcc);
            }
        }
        else if (dfn[v] < dfn[u]) {
            low[u] = min(low[u], dfn[v]);
        }
    }

    if (u == root) {
        if (child_cnt == 0) {
            answer.push_back(vector<int>(1, u));
        }
        else if (child_cnt > 1) {
            is_cut[u] = true;
        }
    }
}

void solve_component(int root) {
    int answer_before = answer.size();
    component_nodes.clear();

    dfs(root, -1, root);

    if (!node_stack.empty() && node_stack.back() == root) {
        node_stack.pop_back();
    }

    bool has_cut = false;
    for (size_t i = 0; i < component_nodes.size(); i++) {
        if (is_cut[component_nodes[i]]) {
            has_cut = true;
            break;
        }
    }

    int new_bcc_cnt = (int)answer.size() - answer_before;
    if (new_bcc_cnt == 1 && !has_cut) {
        sort(answer[answer_before].begin(), answer[answer_before].end());
        if ((int)answer[answer_before].size() > 1) {
            deferred_answer.push_back(answer[answer_before]);
            answer.pop_back();
        }
    }
}

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

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

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

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

    for (size_t i = 0; i < deferred_answer.size(); i++) {
        answer.push_back(deferred_answer[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;
}

brute.cpp 还是 Tarjan 的判定逻辑，但它用递归来写，代码更容易看出“什么时候出栈形成一个点双”。它适合拿来理解和对拍；正式代码之所以不能直接照搬，是因为这题数据到 5e5 个点，递归深度可能直接爆栈。

核心观察和你书里的点双模板一致。

设 u 在 DFS 树里有一个儿子 v。如果：

low[v] >= dfn[u]

说明 v 子树无法绕过 u 回到 u 的祖先。于是 u 就成了这部分图和外界之间的分界点。

这时可以确定一整个点双：

把点栈从栈顶一直弹到 v
再把 u 加进来
这些点共同组成一个点双连通分量

这里和强连通分量、边双有两个关键区别：

点双是“在处理儿子 v 回溯时”形成的，不是等 u 整体回溯完才形成
u 可能属于多个点双，所以 u 不能像 SCC 那样在形成一个分量后就永久出栈

实现上还要补两个细节：

图里可能有重边，不能只写 v != fa，必须记录进入当前点的是哪条边，只跳过它的反向边
正式代码把递归 DFS 改成了显式栈模拟 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
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209#include <bits/stdc++.h>
using namespace std;

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

struct Frame {
    int u;          // 当前点
    int in_edge;    // 进入当前点的边编号
    int iter_edge;  // 当前枚举到哪条边
    int child_cnt;  // DFS 树儿子个数
};

int n, m;

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

// Tarjan 时间戳。
int dfn[MAXN], low[MAXN], dfs_clock;

// DFS 树父子关系。
int parent_node[MAXN], parent_edge[MAXN];

// 标记割点。
bool is_cut[MAXN];

// 点双使用“点栈”维护当前尚未归属的点。
vector<int> node_stack;

// 当前连通块里访问到的点，用来判断这个连通块里是否存在割点。
vector<int> component_nodes;

// 最终答案。
vector< vector<int> > answer;
vector< vector<int> > deferred_answer;

void init_graph() {
    edge_cnt = 0;
    dfs_clock = 0;
    answer.clear();
    deferred_answer.clear();
    node_stack.clear();

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

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

// 处理一个连通块。
// 为了避免 5e5 深度时递归爆栈，这里改成显式栈模拟 DFS。
void solve_component(int root) {
    int answer_before = answer.size();
    component_nodes.clear();

    vector<Frame> call_stack;
    call_stack.push_back({root, -1, head[root], 0});

    parent_node[root] = 0;
    parent_edge[root] = -1;
    dfn[root] = low[root] = ++dfs_clock;
    node_stack.push_back(root);
    component_nodes.push_back(root);

    while (!call_stack.empty()) {
        Frame &cur = call_stack.back();
        int u = cur.u;

        if (cur.iter_edge != -1) {
            int e = cur.iter_edge;
            cur.iter_edge = nxt[e];
            int v = to[e];

            // 只跳过进入当前点那条边的反向边，重边要保留。
            if (e == (cur.in_edge ^ 1)) {
                continue;
            }

            if (!dfn[v]) {
                cur.child_cnt++;
                parent_node[v] = u;
                parent_edge[v] = e;

                call_stack.push_back({v, e, head[v], 0});
                dfn[v] = low[v] = ++dfs_clock;
                node_stack.push_back(v);
                component_nodes.push_back(v);
                continue;
            }

            // 返祖边只能用祖先的 dfn 更新 low。
            if (dfn[v] < dfn[u]) {
                low[u] = min(low[u], dfn[v]);
            }
            continue;
        }

        call_stack.pop_back();

        if (cur.in_edge == -1) {
            // 根节点如果没有 DFS 儿子，说明它是孤立点，
            // 或者只有自环，总之单独构成一个点双。
            if (cur.child_cnt == 0) {
                answer.push_back(vector<int>(1, u));
            }
            else if (cur.child_cnt > 1) {
                is_cut[u] = true;
            }
        }
        else {
            int p = parent_node[u];
            low[p] = min(low[p], low[u]);

            if (low[u] >= dfn[p]) {
                // 非根节点：存在儿子回不到祖先，则它是割点。
                if (parent_edge[p] != -1) {
                    is_cut[p] = true;
                }

                vector<int> bcc;
                while (true) {
                    int x = node_stack.back();
                    node_stack.pop_back();
                    bcc.push_back(x);
                    if (x == u) {
                        break;
                    }
                }
                bcc.push_back(p);
                answer.push_back(bcc);
            }
        }
    }

    // 这个连通块处理结束后，根节点会残留在点栈里，弹掉即可。
    if (!node_stack.empty() && node_stack.back() == root) {
        node_stack.pop_back();
    }

    bool has_cut = false;
    for (size_t i = 0; i < component_nodes.size(); i++) {
        if (is_cut[component_nodes[i]]) {
            has_cut = true;
            break;
        }
    }

    int new_bcc_cnt = (int)answer.size() - answer_before;

    // 如果这个连通块本身就没有割点，那么它只会形成一个点双。
    // 做一次升序整理，并把这种“整块就是一个点双”的答案延后输出，
    // 这样可以和题面样例保持同样的展示顺序。
    if (new_bcc_cnt == 1 && !has_cut) {
        sort(answer[answer_before].begin(), answer[answer_before].end());
        if ((int)answer[answer_before].size() > 1) {
            deferred_answer.push_back(answer[answer_before]);
            answer.pop_back();
        }
    }
}

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

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

    node_stack.reserve(n);
    component_nodes.reserve(n);

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

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

    for (size_t i = 0; i < deferred_answer.size(); i++) {
        answer.push_back(deferred_answer[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;
}

复杂度

每个点进出 DFS 一次，每条边只会被常数次访问，所以：

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

总结

这题的主线可以直接记成一句话：

割点把点双切开，low[v] >= dfn[u] 时，u 和 v 子树的一段点会形成一个新的点双

真正实现时要特别留意三件事：

割点可以属于多个点双，所以 u 不能被永久弹栈
重边要用边编号过滤父边
大数据下递归会爆栈，正式代码最好改成非递归

一图流解析

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

P8435 【模板】点双连通分量

题目背景

点双连通分量的定义是一个极大点双连通子图，而点双连通图的定义存在争议。

一种定义是“图中任意两不同点之间都有至少两条点不重复的路径”，而另外一种是“不存在割点的图”，这两种定义存在细微差别，这里采用后者。

题目描述

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

输入格式

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

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

输出格式

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

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

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

输入输出样例 #1

输入 #1

text

输出 #1

text

1
21
5 1 2 3 4 5

输入输出样例 #2

输入 #2

text

输出 #2

text

输入输出样例 #3

输入 #3

text

输出 #3

text

输入输出样例 #4

输入 #4

text

输出 #4

text

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

输入输出样例 #5

输入 #5

text

1
21 1
1 1

输出 #5

text

1
21
1 1

说明/提示

样例四解释：

相同颜色的点为同一个分量里的结点。

温馨提示：请认真考虑孤立点与自环（样例五）的情况。

数据范围： 对于 $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$ 发现昨天新加入的数据出了问题，已修改。
$2025/10/29$ 追加了一组 hack 数据。

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

【模板】点双连通分量

目录

题意

样例图

思路

代码

复杂度

总结

一图流解析