【模板】点双连通分量

· · 题解

0.前置知识

割点
本题依赖此算法，建议通过此题后在食用~
现在默认我们已经会求割点了。

1.概念

若一个无向图中的去掉任意一个节点都不会改变此图的连通性，即不存在割点，则称作点双连通图。一个无向图中的每一个极大点双连通子图称作此无向图的点双连通分量。

2.性质

点双连通分量有许多性质，可以帮助我们解决这道题。

  1. 图中任意一个割点都在至少两个点双联通分量中。
    因为割点连接了多个点双连通分量（这是由于删掉割点后图会分成多个，且根据定义，点双连通分量中不可能有割点）。
    同样的，点双连通分量之间以割点连接。
    （建议联系样例的图片食用~）

  2. 图中任意一个非割点都在且只在一个点双连通分量之中
    这也标志了图中的孤立点也算一个点双连通分量
    （当然，一个点双连通分量中也可能只有割点，如下图中点0,1,2,3形成的点双连通分量）

3.求法

当然要先求割点啦
我们考虑在利用 Tarjan 求割点时，把遍历到的每个点都加入一个栈中（类似于有向图缩点时的操作）。
当我们在找到一个缩点时，此时栈中，由它生出去的一个子树（虽然实际上不是树，但是请类比概念），便是一个点双连通分量。

注意：与有向图求缩点不同，我们在弹栈时，判断条件为是否到出点而不是是否为源点
我们以样例 3 为例子，并加上 6 5 这条边 （才不是因为我不小心把数据输错了呢）
图中标黑的点为割点

这个图的dfs序（入栈顺序）应为 1 2 3 4 6 5。
依照回溯的思路，我们第一个处理的割点应为 6。
此时 5 是一个“子树”，弹栈，将 6 也加入答案中，我们得到了一个点双 5 6。

此处重点：弹栈时不能弹出割点，因为割点属于多个点双

处理第二个割点4，它的“子树”（在栈中）应为 6，根据回溯的思维，在处理 6 时，以它为割点的点双已经处理完毕，而与割点 4 形成的点双是最后一个点双，可以将 6 出栈，但不能将 4 出栈。我们得到了第二个点双 4 6。

现在处理 2，它有两个“子树”：3 4。

在处理 4 时，我们不能将 3 也出栈，因为他不在 4 的“子树”上。

最后是一个不同的地方，在处理根节点时，无论它是否为割点，一律出栈。

附代码 

#include<bits/stdc++.h>
using namespace std;
int n,m,low[500005],dfn[500005],ans,cnt;
int nxt[4000005],head[500005],go[4000005],k;
vector<int> dcc[500005];
stack<int>sta;
void add(int u,int v)
{
    nxt[++k]=head[u];
    head[u]=k;
    go[k]=v;
}
void tarjan(int x,int root)//求割点的改版（其实不需要root）
{
    dfn[x]=low[x]=++cnt;
    if(x==root&&!head[x])//孤立点判定
    {
        dcc[++ans].push_back(x);
    }
    sta.push(x);
    for(int i=head[x];i;i=nxt[i])
    {
        int g=go[i];
        if(!dfn[g])
        {
            tarjan(g,root);
            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);//注意此处，因为要求是不到达出点
                dcc[ans].push_back(x);//别忘了加入源点！
            }
        }
        else
        low[x]=min(low[x],dfn[g]);
    }
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        int x,y;
        cin>>x>>y;
        if(x==y) continue;//重边
        add(x,y);
        add(y,x);
    }
    for(int i=1;i<=n;i++)
    {
        if(!dfn[i]) tarjan(i,i);//注意图可能不连通
    }
    cout<<ans<<endl;
    for(int i=1;i<=ans;i++)
    {
        cout<<dcc[i].size()<<" ";
        for(int j=0;j<dcc[i].size();j++)
        cout<<dcc[i][j]<<" ";
        cout<<endl;
    }
}