P8436 【模板】边双连通分量

· · 题解

2022/8/20 修改：对于 SCC 部分的说明不严谨，已修正

Tarjan-E-DCC 求无向图边双联通分量(E-DCC)的算法

求解无向图的边双联通分量有两种方法，有一种很好理解的办法是：由于边双联通分量中不存在桥，所以实质上只需要把桥全部求出来再跑一遍不过桥的 dfs 即可求出边双联通分量。

void tarjan(int x,int father){
    dfn[x]=low[x]=++nowtime;
    for(register int i=head[x];i;i=e[i].next){
        int v(e[i].to);
        if(!dfn[v]){
            tarjan(v,i);
            low[x]=min(low[x],low[v]);
            if(low[v]>dfn[x])bridges[i]=bridges[i^1]=true;
        }else if(i!=(father^1))low[x]=min(low[x],dfn[v]);
    }
}
void dfs(int x){
    vis[x]=1;
    for(register int i=head[x];i;i=e[i].next){
        if(bridges[i])continue;
        int v(e[i].to);
        if(!vis[v])dfs(v);
    }
}
int main(){
    for(register int i=1;i<=n;++i)
        if(!dfn[i])tarjan(i,i);
    for(register int i=1;i<=n;++i)
        if(!vis[i]){
            dfs(i);
            ++dcccnt;
        }
}

第二种求解方法可以联系求解 SCC 时的知识理解：在求桥时限制了返回父亲的返祖边的情况下，在选定 root 节点之后，一张无向图已经变成了一张有向图（实际上这张有向图就是搜索树），往什么方向走，什么地方会在搜索树上形成有向环，都已经是固定下来的了。因此我们可以仿照求 SCC 时的思路，在一个强连通分量中的点可以互相到达，而处于两个不同强连通分量中的点不能相互到达，而边双联通分量恰好是没有桥的联通分量，我们引出一个非常容易想的结论：在无向图中只要一个分量中没有桥，那么该分量在 Tarjan-Bridge 算法抽象出的有向图中一定强连通，反过来说，被抽象为有向图的无向图中的一个强连通分量，在原图中是一定一个边双联通分量。因此在已经被抽象成有向图的无向图中，我们只需求出强连通分量就恰恰是边双联通分量。

对上述结论作一个简要但不严谨的说明：考虑 Tarjan-Bridge 算法实际上抽象出的有向图实际上就是一棵搜索树，而在该搜索树上构成环当且仅当出现返祖边，即在无向图中该分量内不会出现桥，容易发现的是搜索树最终可以被划分为类似环-桥-环的结构，与边双联通分量的定义实际上是相符的。关于其为什么是极大的，这点可以参照对于求 SCC 算法中解释“为什么环内路径不影响结果”的方法。

这样想的话，实际上这种方法是把无向图抽象为有向搜索树，通过搜索树的性质利用对于有向图求 SCC 的方法求出边双联通分量，这种抽象方式令人拍手称妙。

代码如下：

void tarjan(int x,int father){
    dfn[x]=low[x]=++nowtime;
    s.push(x);
    for(register int i=head[x];i;i=e[i].next){
        int v(e[i].to);
        if(!dfn[v]){
            tarjan(v,i);
            low[x]=Min(low[x],low[v]);
        }else if(i!=(father^1))low[x]=Min(low[x],dfn[v]);
    }
    if(dfn[x]==low[x]){
        ++dcccnt;
        int k;
        do{
            k=s.pop();
            belong[k]=dcccnt;
        }while(k!=x);
    }
}
int main(){
    for(register int i=1;i<=n;++i)
        if(!dfn[i])tarjan(i,i);
}