点双连通分量和边双连通分量学习笔记

1.简介：

对于一个连通图，如果任意两点至少存在两条点不重复路径，则称这个图为点双连通的（简称双连通）；如果任意两点至少存在两条边不重复路径，则称该图为边双连通的。点双连通图的定义等价于任意两条边都同在一个简单环中，而边双连通图的定义等价于任意一条边至少在一个简单环中。对一个无向图，点双连通的极大子图称为点双连通分量（简称双连通分量），边双连通的极大子图称为边双连通分量。

而在每一个点双连通图中，内部无割点；

在每一个边双连通图中，内部无桥。

如图：

 

 

1、2、3，2、4、5为两个点双连通分量，1、2、3、4、5却在一个边双连通分量中；其中，3为割点。

而第二个图中，2-6边为桥。

 

2.性质：

  <1>.点双连通分量:

     (1).点双连通分量之间以割点连接，且两个点双连通分量之间有且只有一个割点。

         证明：

            若两个点双连通分量之间共用两个点，则删除其中任意一个点，所有点依旧连通。

         如图：

                        

     (2).每一个割点可任意属于多个点双连通分量，因此求点双连通分量时，可能包含重复的点。

             (3).只有一条边连通的两个点也是一个点双连通分量，如：

        

         所以，在下图中，存在（1、2、3）,（3、4），（4、5、6）三个点双连通分量。

         

     (4).对于此点为根的情况，第一个儿子也属于点双连通分量，故不能用判断割点的方法来判断，

         只要dfn[父]<=low[子]，便可将其加入点双：

        

 

                在此图中，1、2、3、4在同一个点双连通分量里，但2是1的第一个儿子

    (5).对于删去此点不会不与祖辈连通的儿子，在处理其他儿子的点双连通分量时，不能将其删去，如。

        

 

                    1、2、3共同构成一个点双连通分量，不能在处理4、5、6是将其删去。

                    所以代码不该为：

                    

while(s[top]!=u) ++siz[tot]=s[top],num[s[top]]=tot,--top;

                   而应是

                   

v=e[i].to;        while(s[top+1]!=v) ++siz[tot],num[s[top]]=tot,--top;

       <2>.边双连通分量：

        可将图看作森林，节点为边双连通分量，树边为桥:

               

        第二张图是第一张图中的点双连通分量缩点后的样子。

 

     边双连通分量没有什么性质，反正也很简单。                   ——LY巨佬

3.做法和代码:

    日复一日的神仙tarjan算法：

     1>.点双连通分量：

        用栈来储存，按dfs序来加点，将此点与low小于其dfn的点放入一个点双连通分量中（注：此点不退栈）

        

1 void tarjan(int u) 2 { 3     dfn[u]=low[u]=++deep; s[++top]=u; int o=0,v; 4     for(int i=head[u];i;i=e[i].nxt) 5     { 6         v=e[i].to; 7         if(!dfn[v]) 8         { 9             ++o;10             tarjan(v),low[u]=min(low[u],low[v]);11             if(low[v]>=dfn[u])12             {13                 if(u!=fa) cut[u]=1; ++tot;14                 while(s[top+1]!=v) num[tot][++siz[tot]]=s[top],id[s[top]]=tot,--top;15                 num[tot][++siz[tot]]=u;//将id[u]默认属于它父亲的tot了16             }17         }18         else low[u]=min(low[u],dfn[v]);19     }20     if(u==fa&&o>=2) cut[u]=1;21 }

 

     2>.边双连通分量：

        删去桥就行了。

 

1 #include
      
        2 using namespace std; 3 const int N=5006,M=10006; 4 int head[N],cnt=1,n,m,t1,t2,book[N],dfn[N],low[N],deep=0,v[M*2],f[N],tot=0,d[N],g[N],p=0,num[N][N],siz[N]; 5 map
       
         ha[N]; 6 int getf(int u){
    return g[u]==u?u:g[u]=getf(g[u]);} 7 void merge(int u,int v) 8 { 9     u=getf(u); v=getf(v);10     if(u==v) return;11     g[u]=v;12 }13 struct edge14 {15     int nxt,to;16 }e[M*2]; 17 inline int read()18 {19     int T=0,F=1; char ch=getchar();20     while(ch<'0'||ch>'9'){
    if(ch=='-') F=-1; ch=getchar();}21     while(ch>='0'&&ch<='9') T=(T<<3)+(T<<1)+(ch-48),ch=getchar();22     return F*T;23 }24 inline void add(int u,int v){e[++cnt].nxt=head[u]; e[cnt].to=v; head[u]=cnt;} 25 void tarjan(int u)26 {27     dfn[u]=low[u]=++deep;28     for(int i=head[u];i;i=e[i].nxt)29     {30         if(v[i^1]||v[i]) continue;31         if(!dfn[e[i].to]) v[i]=1,f[e[i].to]=u,tarjan(e[i].to),low[u]=min(low[u],low[e[i].to]);32         else low[u]=min(low[u],dfn[e[i].to]);33     }34 }35 int main()36 {37     n=read(),m=read();38     for(int i=1;i<=n;++i) g[i]=i;39     for(int i=1;i<=m;++i) t1=read(),t2=read(),add(t1,t2),add(t2,t1);40     for(int i=1;i<=n;++i) if(!dfn[i]) tarjan(i);41     for(int i=1;i<=n;++i) if(f[i]&&low[i]>dfn[f[i]]) ++tot,ha[i][f[i]]=1,ha[f[i]][i]=1;42     for(int i=1;i<=n;++i)43         for(int j=head[i];j;j=e[j].nxt) if(ha[i].find(e[j].to)==ha[i].end()) merge(i,e[j].to);44     for(int i=1;i<=n;++i) g[i]=getf(i);45     for(int i=1;i<=n;++i)46     {47         if(!book[g[i]]) ++p,d[g[i]]=p,book[g[i]]=1;48         g[i]=d[g[i]],num[g[i]][++siz[g[i]]]=i;49     } 50     printf("共有%d个边双连通分量\n",p);51     for(int i=1;i<=p;++i)52     {53         printf("第%d个边双连通分量共有%d个点",i,siz[i]);54         for(int j=1;j<=siz[i];++j) printf("%d ",num[i][j]);55         printf("\n");56     }57     return 0;58 }