【模板】点双连通分量

无向图割点算法的一个拓展

概念

什么是点双连通分量？

在无向图中，如果对于任意一个点A和点B，他们之间可以有两条不同的路径连通，那么点A和点B就是一个点双连通分量（以下简称点双）。如下图，A可以经过D或者C到达B点。

但是，我们一般求解的是极大的点双连通分量。

什么意思呢？

就是求子图，对于这一整个子图都能满足上面所说的性质，并将子图内的点保存下来。

性质

1. 在点双内，删去任一 一个点之后，整个图都是连通的。
2. 点双内的任一两点，都有两条以上的不同的路线

求解方法

1.在割点的同时记录该点的父亲和孩子数量。 2.当这个u点为割点的时候，那么意味着它此后的子图中所有的点 到 u 都必须经过这个点v，那么与v相连的子图肯定不能和u是一个点双内。并且v所在的子图经过的点都已经保存下来了，那么这个子图就是一个点双。 3.当根节点的儿子数为0的时候，他自己就是一个点双。

Code

#include<bits/stdc++.h>
using namespace std;
const int N=5e5+12,M=4e6+12;
int cnt=1;
int s[M],top,bcc,low[N],dfn[N],idx,n,m;

vector<int>ans[N];
vector<int>e[N];

void tarjan(int u,int fa)
{
  int son=0;
  low[u]=dfn[u]=++idx;
    s[ ++top ]=u;
  for( auto v:e[u] )
  {
    if( !dfn[v] )
    {
      son++;
      tarjan(v,u);
      low[u]=min( low[u],low[v] );
      if( low[v]>=dfn[u] )
      {
        bcc++;
        while( s[top+1]!=v ) ans[ bcc ].push_back( s[top--] );
        ans[ bcc ].push_back(u);
      }
    }
    else if( v!=fa )
    {
      low[u]=min( low[u],dfn[v] );
    }
  }
  if( fa==0 && son==0 ) ans[++bcc].push_back(u);
}

int main(){
  cin>>n>>m;
  for(int i=1;i<=m;i++)
  {
    int u,v;
    cin>>u>>v;
    e[ u ].push_back(v);
    e[ v ].push_back(u);
  }
  for(int i=1;i<=n;i++)
  {
    if( !dfn[i] )
    {
      tarjan(i,0);
    }
  }
  cout<<bcc<<endl;
  for(int i=1;i<=bcc;i++)
  {
    cout<<ans[i].size()<<" ";
    for(int j:ans[i]) cout<<j<<" ";
    cout<<endl;

  }
}

边双连通分量

边双连通分量与点双的做法基本上一样，不过注意：在寻找边双的时候，我们需要同时将反向边打上标记,为了能快速的给反向边打上标记，我们从$cnt=1$时开始建图，这样第一次建图的时候 标号就是 2&3 他们异或1后都等于对方。

Code

#include<bits/stdc++.h>
using namespace std;
const int N=5e5+12,M=4e6+12;

struct{
  int to,nex;
}edge[M];

int cnt=1,m,n,idx,sum;
int head[N],dfn[N],low[N],dcc[N];
vector<int>ans[N];
bool b[M];

void addedge(int u,int v)
{
  cnt++;
  edge[cnt]={ v,head[u] };
  head[u]=cnt;
}

void tarjan(int x,int p)
{
  dfn[x]=low[x]=idx++;
  for(int i=head[x];i;i=edge[i].nex)
  {
    int y=edge[i].to;
    if( !dfn[y] )
    {
      tarjan(y,i);
      low[x]=min(low[x],low[y]);
      if( low[y]>=dfn[x] )
        b[i]=b[i^1]=1;
    }
    else if( i!=(p^1) )
    {
      low[x]=min(low[x],dfn[y]);
    }
  }
}

void dfs(int x,int now)
{
  dcc[x]=now;
  ans[ now ].push_back( x );
  for(int i=head[x];i;i=edge[i].nex)
  {
    int y=edge[i].to;
    if( dcc[y] || b[i] ) continue;
    dfs(y,now);
  }
}


int main(){
  cin>>n>>m;
  for(int i=1;i<=m;i++)
  {
    int u,v;
    cin>>u>>v;
    if(u==v) continue;
    addedge(u,v);
    addedge(v,u);
  }
  for(int i=1;i<=n;i++) if( !dfn[i] ) tarjan(i,0);

  for(int i=1;i<=n;i++) if( !dcc[i] ) dfs(i,++sum);

  cout<<sum<<endl;

  for(int i=1;i<=sum;i++)
  {
    cout<<ans[i].size()<<" ";
    for( auto y:ans[i] )
    {
      cout<<y<<" ";
    }

    cout<<endl;

  }



}