【题解】P8436 【模板】边双连通分量

· · 题解

OI-wiki 上的参考资料

看上去大家都使用的是 tarjan 算法来求边双连通分量。但其实对于边双连通分量，我们有其他的做法。下面介绍的做法（个人认为）码量不大，并且思想比 tarjan 算法简单一些。

考虑对无向图进行 dfs，得到一棵 dfs 树。

我们考虑每一条不在树上的边 (u,v)，很明显，这条边和 u,v 在树上的路径构成了一个环。因此此时这条边和它在树上对应的路径都不会是割边。于是我们对于每条不在 dfs 树上的边标记好它在树上对应的路径，这样未被标记到的边就是割边。

放一张图以便理解。（图源 OI-wiki）

红色的边是不在 dfs 树上的边。对于每条红边我们将树上对应的路径打好标记（用绿色表示）。于是剩余的黑色的边就是割边。

接下来我们考虑如何快速地标记树上的路径。做树上差分即可。

注意到无向图上的 dfs 树有优秀的性质，非树边不会有横叉边，只会有儿子和祖先相连的边（否则我们可以继续沿横叉边 dfs，这违反了 dfs 树的定义）。

因此我们我们就省去了求 LCA 的步骤。对于每一条非树边，直接在深度较大的结点上加 1，在深度较小的结点减 1，就完成了树上差分。所有的非树边都处理完后，我们做一下子树和，此时结点值为 0 的结点到它的父亲的边就是割边。

求出割边之后将割边删去，剩下的部分就是一个个边双连通分量了。

最后我们给出代码实现。更多细节见注释。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <cctype>
#include <vector>
using namespace std;
const int maxn=500010,maxm=2000010;
inline int read()
{
    int ret=0,f=1;char ch=getchar();
    while(!isdigit(ch)){if(ch=='-')f=-f;ch=getchar();}
    while(isdigit(ch)){ret=ret*10+ch-'0';ch=getchar();}
    return ret*f;
}
//cnt=1是为了方便之后e[i^1]查反边
//treecnt是图中dfs树的数量（因为原图可能不连通），rt是每棵树的根
//bcccnt是图中边双连通分量的数量
//vis为访问标记，w是点权（做差分用），dep为结点在树中的深度，fa为结点在树中的父亲
//另外无向图记得两倍空间
int n,m,cnt=1,treecnt,bcccnt,h[maxn<<1],vis[maxn],w[maxn],dep[maxn],rt[maxn],fa[maxn];
vector<int> bcc[maxn];//存边双连通分量
struct edge{int to,nxt,val;}e[maxm<<1];//这里给边设置了一个标记，1为树边，0为非树边，-1为割边
void addedge(int u,int v,int val)
{
    e[++cnt]=(edge){v,h[u],val};
    h[u]=cnt;
}
void dfs1(int u)//第一次dfs求出dfs树及相关的值
{
    vis[u]=1;
    for(int i=h[u];i;i=e[i].nxt)
    {
        int p=e[i].to;
        if(!vis[p])
        {
            e[i].val=e[i^1].val=1;
            dep[p]=dep[u]+1;
            fa[p]=u;
            dfs1(p);
        }
    }
}
void dfs2(int u)//第二次dfs做子树和
{
    for(int i=h[u];i;i=e[i].nxt)
        if(e[i].val)
        {
            int p=e[i].to;
            if(p!=fa[u])
            {
                dfs2(p);
                w[u]+=w[p];
            }
        }
}
void dfs3(int u)//第三次dfs统计边双连通分量
{
    vis[u]=1;bcc[bcccnt].push_back(u);
    for(int i=h[u];i;i=e[i].nxt)
    {
        if(e[i].val==-1)continue;//遇到割边就跳过
        int p=e[i].to;
        if(!vis[p])dfs3(p);
    }
}
int main()
{
    n=read();m=read();
    for(int i=1;i<=m;i++)
    {
        int u=read(),v=read();
        addedge(u,v,0);addedge(v,u,0);
    }
    for(int i=1;i<=n;i++)
        if(!vis[i])
        {
            rt[++treecnt]=i;
            dfs1(i);
        }
    for(int u=1;u<=n;u++)
        for(int i=h[u];i;i=e[i].nxt)
            if(!e[i].val)//若该边为非树边则做差分
            {
                int p=e[i].to;
                if(dep[p]<dep[u]){w[p]--;w[u]++;}//上面已有对这样写的解释。
                //注意这里我们只考虑了dep[p]<dep[u]的情况，这是因为所有的边都是双向边，我们只需统计一次
            }
    for(int i=1;i<=treecnt;i++)dfs2(rt[i]);
    for(int u=1;u<=n;u++)
        if(!w[u])//点权为0则与父亲之间的边为割边
            for(int i=h[u];i;i=e[i].nxt)
                if(e[i].val&&e[i].to==fa[u])
                    e[i].val=e[i^1].val=-1;
    memset(vis,0,sizeof(vis));
    for(int i=1;i<=n;i++)
        if(!vis[i])
        {
            ++bcccnt;
            dfs3(i);
        }
    printf("%d\n",bcccnt);
    for(int i=1;i<=bcccnt;i++)
    {
        printf("%d ",bcc[i].size());
        for(auto it:bcc[i])printf("%d ",it);
        printf("\n");
    }
    return 0;
}