【模板】边双连通分量

· · 题解

修复了英文与中文间的空格

orz 题解区的神犇已经将桥和边双的基本做法讲明白了，那本蒟蒻就写一种别的做法吧。

利用栈存储答案

这种做法与点双 十分类似，都是将遍历到的点依次加入栈，并在找到一个桥时，将栈中的存储的节点弹出作为一个边双的答案，仅在细节处理时有些变化。

  1. 记录答案时（找到桥时）不再记录当前节点。
    这个很显然吧，毕竟这条桥就是用来区分边双的。
  2. 若图中不存在桥时
    我们在求点双时，暴力地将割点的条件直接修改为 low[v]>=dfn[u] 而省略根节点的判断。这样我们可以将剩余的节点与根节点一起放入一个点双。
    但很显然，如果图中不存在桥，就不可能使条件 low[v]>dfn[u] 成立
    我们考虑在每一次搜索前，建立一个虚拟源点指向原来的根（单向双向均可，因为正常的 Tarjan 本来就不要求走回头路），让这个虚拟节点成为新的根。这样，原先我们新加的虚拟边就成为了虚拟桥。这样就使图中至少存在一个桥。也可以解决独立节点的问题。

下面是代码

#include<bits/stdc++.h>
using namespace std;
int n,m,nxt[4100005],head[2000005],k=1,cnt,go[4100005],dfn[2000005],low[2000005],ans;
vector<int> dcc[500005];
void add(int x,int y)
{
    nxt[++k]=head[x];
    head[x]=k;
    go[k]=y;
}
stack<int>sta;
void tarjan(int x,int edge)
{
    dfn[x]=low[x]=++cnt;
    sta.push(x);
    for(int i=head[x];i;i=nxt[i])
    {
        int g=go[i];
        if(!dfn[g])
        {
            tarjan(g,i);
            low[x]=min(low[x],low[g]);
            if(low[g]>dfn[x])//非常正常的求桥
            {
                ans++;
                int p;
                do{
                    p=sta.top();
                    sta.pop();
                    dcc[ans].push_back(p);
                }while(p!=g);//记录答案
           //这里不再需要加入当前节点了
            }
        }
        else if(i!=(edge^1))  //不走回头路
        low[x]=min(low[x],dfn[g]);
    }
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++)
    {
        int u,v;
        scanf("%d%d",&u,&v);
        if(u==v) continue;//重边
        add(u,v);
        add(v,u);
    }
    for(int i=1;i<=n;i++)
    {
        if(!dfn[i]) 
        {
            add(i+n,i);//虚拟点tarjan
            tarjan(i+n,0);
        }
    }
    printf("%d\n",ans);
    for(int i=1;i<=ans;i++)
    {
        printf("%d ",dcc[i].size());
        for(int j=0;j<dcc[i].size();j++)
        printf("%d ",dcc[i][j]);
        puts("");
    }
}

相对于割裂出来各个子图，在进行搜索的做法，省略了一次搜索和两个标记数组。但是导致了边数和点数的增多以及在原来的 Tarjan 需进行栈操作，也许互有优劣？