一 解题思路

边双连通分量其实是割边的升级版，多几行代码，这里我就先介绍割边的求法，再介绍边双连通分量的求法。

求割边

求割边所用的是 tarjan 算法，其本质是根据“追溯值”来判断某一条边能割去图是否依然连通。

这里我们引入两个数组：

简单来说，追溯值记录的是某节点通过一条不在子树上的边“向上”能到达的最小编号结点。

在初始的情况下，low_x = dfn_x 也就是某个点的追溯值最开始是自己。

比如这就是样例中图的 low、dfn 的信息。

追溯值数组的更新有以下两种可能的情况（为了方便表示，我们令 x 结点有一条边连向 y 结点）：

• 如果 y 是 x 搜索树上的结点（还没有被标记时间戳）那么，low_x = \min(low_x, low_y)。
• 否则（y 不是搜索树上的结点） low_x = \min(low_x, dfn_y)

注意：后者是 dfn_y

通过一条不在搜索树上的边

只有一条!

割边的判定:

如果 x 到 y 的无向边是割边，当且仅当（充要条件） dfn_x \lt low_y

解释：如果从 x 经过一条“回边”到不了 y，那么显然这是一条割边。

请还是看上面那张图，画上红线的就是割边，把它切断后，就会使得某个点无法回到自己/上面的点，所以这一条边删去后，图就不再连通。

注意：后者是 dfn_y

代码实现时有一个小技巧，就是建图时边的编号从 2 开始标，这样就能以 O(1) 的时间复杂度求出某边的逆向边（异或运算），并且标记割边。

求双联通分量

由于边双连通分量中去除任意一条边后，分量依然是连通的，所以边双连通分量中没有割边（与点双连通分量不同），因此我们就可以把所有割边“拆掉”，来求边双连通分量。

图片解释：

请您看，把割边去掉后，不就剩下连通分量了吗？

当我们求出割边后，我们可以使用这样一个 dfs 来分离出所有边双连通分量：

void dfs(int node, int ndcc)
{
    dcc[node] = ndcc;
    Ans[ndcc - 1].push_back(node);
    for (int i = head[node]; i; i = e[i].nxt)
    {
        int to = e[i].to;
        if (dcc[to] || b[i]) continue;
        // 如果这个点属于其他分量或者这条边是割边，就停止搜索。
        dfs(to, ndcc);
    }
}

二 代码

#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
const int maxn = 500010, maxm = 4000010;
int n, m, cnt = 1, ans, id;
int dfn[maxn], low[maxn], head[maxn], dcc[maxn];
struct edge
{
    int to, nxt;
}e[maxm];
bool b[maxm];
vector <vector <int> > Ans;
void add(int f, int t)
{
    e[++cnt].to = t;
    e[cnt].nxt = head[f];
    head[f] = cnt;
}
void tarjan(int node, int in_edge)
{
    dfn[node] = low[node] = ++id;
    for (int i = head[node]; i; i = e[i].nxt)
    {
        const int to = e[i].to;
        if (dfn[to] == 0)
        {
            tarjan(to, i);
            if (dfn[node] < low[to])
                b[i] = b[i ^ 1] = 1;
            low[node] = min(low[node], low[to]);
        }
        else if (i != (in_edge ^ 1))
            low[node] = min(low[node], dfn[to]);
    }
}
void dfs(int node, int ndcc)
{
    dcc[node] = ndcc;
    Ans[ndcc - 1].push_back(node);
    for (int i = head[node]; i; i = e[i].nxt)
    {
        int to = e[i].to;
        if (dcc[to] || b[i]) continue;
        dfs(to, ndcc);
    }
}
int main()
{
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= m; ++i)
    {
        int f, t;
        scanf("%d %d", &f, &t);
        if (f == t) continue;
        add(f, t);
        add(t, f);
    }
    for (int i = 1; i <= n; ++i)
        if (dfn[i] == 0)
            tarjan(i, 0);
    for (int i = 1; i <= n; ++i)
        if (dcc[i] == 0)
        {
            Ans.push_back(vector <int>());
            dfs(i, ++ans);
        }
    printf("%d\n", ans);
    for (int i = 0; i < ans; ++i)
    {
        printf("%d", Ans[i].size());
        for (int j = 0; j < Ans[i].size(); ++j)
            printf(" %d", Ans[i][j]);
        printf("\n");
    }
    return 0;
}

三 说明

本题解中的部分内容引自《算法竞赛进阶指南》，而大部分内容为作者学习后自我归纳的产物。

四 提示（常见的错误）

说明：本部分部分内容总结自讨论区。

• 测试点 1、2 Wrong Answer：图可能有重边，请用合适的存图方式。

• 测试点 9、10 TLE/MLE：建议使用二维 vector，数据中存在某些分量只存在一个点，而分量很多的情况。

五 Hack 数据征集

我是题目提供者，如果您有 hack 数据，请在此处回复并 at 我，我将会把 hack 数据加入测试数据中。

反馈 hack 数据要求：

• 给出被 hack 的代码的链接

• 给出数据（如果数据过大可以提供生成器）

• hack 前自查数据是否符合数据范围

感谢您的贡献。