[点连通度与边连通度]

在一个无向连通图中，如果有一个顶点集合，删除这个顶点集合，以及这个集合中所有顶点相关联的边以后，原图变成多个连通块，就称这个点集为割点集合。一个图的点连通度的定义为，最小割点集合中的顶点数。

类似的，如果有一个边集合，删除这个边集合以后，原图变成多个连通块，就称这个点集为割边集合。一个图的边连通度的定义为，最小割边集合中的边数。

 

1 int dfn[maxn],low[maxn]; 2 int t=0; 3  4 void Tarjan(int u,int p) 5 { 6     dfn[u]=low[u]=++t; 7      8     int child=0; 9     10     for(int i=head[u];i!=-1;i=E[i].next)11     {12         int v=E[i].v;13         14         if(v==p) continue;//避免回连15         16         17         if(!dfn[v])18         {
    //树边19             Tarjan(v,u);20             child++;21             low[u]=min(low[u],low[v]);22             23             if((u==p && child>1) || (u!=p && low[v]>=dfn[u]))24                 cout<<"割点"<<

1 #include 
      
        2 #include 
       
         3  4 using namespace std; 5  6 bool adj[10][10]; 7 int visit[10]; 8 int grand[10]; 9 10 int t=0;11 12 void DFS(int p,int i)13 {14     visit[i]=++t;15     grand[i]=i;16     17     int child=0;18     bool ap=false;19     20     for(int j=0;j<10;j++)21         if(adj[i][j] && j!=p)22         {23             if(visit[j])24             {25                 if(visit[j]
        
         visit[grand[j]])34                     grand[i]=grand[j];35                 36                 if(visit[grand[j]]>=visit[i])37                     ap=true;38             }39         }40     41     if((i==p && child>1) || (i!=p && ap))42         cout<<"第"<
         <<"点是关节点"<
        
       
      

1 int dfn[maxn],low[maxn]; 2 int t=0; 3 //low相同的为同一联通块，为缩点之后的。 4 void Tarjan(int u,int p) 5 { 6     dfn[u]=low[u]=++t; 7      8     int child=0; 9     10     for(int i=head[u];i!=-1;i=E[i].next)11     {12         int v=E[i].v;13         14         15         16         if(!dfn[v])17         {
    //树边18             Tarjan(v,u);19             low[u]=min(low[u],low[v]);20             21         }22         else if(v!=p)23             low[u]=min(low[u],dfn[v]);24     }25 }

1 #include 
      
        2 #include 
       
         3  4 using namespace std; 5  6  7 int adj[10][10]; 8 int visit[10]; 9 int low[10];10 11 int t=0;12 13 void DFS(int p,int i)14 {15     visit[i]=low[i]=++t;16     17     for(int j=0;j<10;j++)18         if(adj[i][j])19         {20             if(!visit[j])21             {22                 DFS(i,j);23                 24                 low[i]=min(low[i],low[j]);25                 26                 if(low[j]>visit[i])27                     cout<<"bridge:"<
        <<"---"<
         
          <
          
           =2))30             {31                 low[i]=min(low[i],low[j]);32             }33         }34 }35 36 void bridge()37 {38     memset(visit,0,sizeof(visit));39     t=0;40     41     for(int i=0;i<10;i++)42         if(!visit[i])43             DFS(i,i);44 }45 46 int main()47 {48     int a,b;49     memset(adj,0,sizeof(adj));50     for(int i=0;i<11;i++)51     {52         scanf("%d%d",&a,&b);53         adj[a][b]=adj[b][a]=1;54     }55     bridge();56     return 0;57     58 }59 60 bridge
          
         
       
      

 

[双连通图、割点与桥]

如果一个无向连通图的点连通度大于1，则称该图是点双连通的(point biconnected)，简称双连通或重连通。一个图有割点，当且仅当这个图的点连通度为1，则割点集合的唯一元素被称为割点(cut point)，又叫关节点(articulation point)。

如果一个无向连通图的边连通度大于1，则称该图是边双连通的(edge biconnected)，简称双连通或重连通。一个图有桥，当且仅当这个图的边连通度为1，则割边集合的唯一元素被称为桥(bridge)，又叫关节边(articulation edge)。

可以看出，点双连通与边双连通都可以简称为双连通，它们之间是有着某种联系的，下文中提到的双连通，均既可指点双连通，又可指边双连通。

 

 

[双连通分支]

在图G的所有子图G'中，如果G'是双连通的，则称G'为双连通子图。如果一个双连通子图G'它不是任何一个双连通子图的真子集，则G'为极大双连通子图。双连通分支(biconnected component)，或重连通分支，就是图的极大双连通子图。特殊的，点双连通分支又叫做块。

[求割点与桥]

该算法是R.Tarjan发明的。对图深度优先搜索，定义DFS(u)为u在搜索树（以下简称为树）中被遍历到的次序号。定义Low(u)为u或u的子树中能通过非父子边追溯到的最早的节点，即DFS序号最小的节点。根据定义，则有：

Low(u)=Min { DFS(u) DFS(v) (u,v)为后向边(返祖边) 等价于 DFS(v)<DFS(u)且v不为u的父亲节点 Low(v) (u,v)为树枝边(父子边) }

一个顶点u是割点，当且仅当满足(1)或(2) (1) u为树根，且u有多于一个子树。 (2) u不为树根，且满足存在(u,v)为树枝边(或称父子边，即u为v在搜索树中的父亲)，使得DFS(u)<=Low(v)。

一条无向边(u,v)是桥，当且仅当(u,v)为树枝边，且满足DFS(u)<Low(v)。

[求双连通分支]

下面要分开讨论点双连通分支与边双连通分支的求法。

对于点双连通分支，实际上在求割点的过程中就能顺便把每个点双连通分支求出。建立一个栈，存储当前双连通分支，在搜索图时，每找到一条树枝边或后向边(非横叉边)，就把这条边加入栈中。如果遇到某时满足DFS(u)<=Low(v)，说明u是一个割点，同时把边从栈顶一个个取出，直到遇到了边(u,v)，取出的这些边与其关联的点，组成一个点双连通分支。割点可以属于多个点双连通分支，其余点和每条边只属于且属于一个点双连通分支。

1 #include 
      
        2 #include 
       
         3 #include 
        
          4 #include 
         
           5 #include 
          
            6  7 #define maxn 10010 8  9 struct edge10 {11     int v,next;12 };13 struct node14 {15     int cnt,u;16 };17 18 19 using namespace std;20 edge E[10*maxn+5];//注意最多有十条边相连，对于每个点／re了几次?21 node G[maxn];22 int head[maxn];23 int n,m,tp,t,ans;24 int dfn[maxn],low[maxn];25 26 void add_edge(int u,int v)27 {28     E[tp].v=v;29     E[tp].next=head[u];30     head[u]=tp++;31 }32 33 bool cmp(node a,node b)//题目要求排序34 {35     if(a.cnt==b.cnt) return a.u
           
            b.cnt;37 }38 void Tarjan(int u,int p)//求割点39 {40 dfn[u]=low[u]=++t;41 42 int child=0;43 for(int i=head[u];i!=-1;i=E[i].next)44 {45 int v=E[i].v;46 if(v==p) continue;47 if(!dfn[v])48 {49 Tarjan(v,u);50 child++;51 low[u]=min(low[u],low[v]);52 53 if((u==p && child>1) || (u!=p && low[v]>=dfn[u]))54 G[u].cnt++;//把割点和与之相连的边去掉之后能形成几个联通块55 }56 else if(v!=p)57 {58 low[u]=min(low[u],dfn[v]);59 }60 }61 62 }63 64 void output()65 {66 sort(G,G+n,cmp);//打印输出前m个数值67 for(int i=0;i
           
          
         
        
       
      

1 void Tarjan(int u,int p) 2 { 3     dfn[u]=low[u]=++t; 4     for(int i=head[u];i!=-1;i=E[i].next) 5     { 6         int v=E[i].v; 7          8         if(!dfn[v])//如果为树边 9         {10             Tarjan(v,u);11             low[u]=min(low[u],low[v]);12         }13         else if(v!=p)//不走回头路且为后向边14         {15             low[u]=min(low[u],dfn[v]);16         }17     }18     if(dfn[u]==low[u])19         ans++;//边联通块数20 }

 

对于边双连通分支，求法更为简单。只需在求出所有的桥以后，把桥边删除，原图变成了多个连通块，则每个连通块就是一个边双连通分支。桥不属于任何一个边双连通分支，其余的边和每个顶点都属于且只属于一个边双连通分支。

[构造双连通图]

一个有桥的连通图，如何把它通过加边变成边双连通图？方法为首先求出所有的桥，然后删除这些桥边，剩下的每个连通块都是一个双连通子图。把每个双连通子图收缩为一个顶点，再把桥边加回来，最后的这个图一定是一棵树，边连通度为1。

统计出树中度为1的节点的个数，即为叶节点的个数，记为leaf。则至少在树上添加(leaf+1)/2条边，就能使树达到边二连通，所以至少添加的边数就是(leaf+1)/2。具体方法为，首先把两个最近公共祖先最远的两个叶节点之间连接一条边，这样可以把这两个点到祖先的路径上所有点收缩到一起，因为一个形成的环一定是双连通的。然后再找两个最近公共祖先最远的两个叶节点，这样一对一对找完，恰好是(leaf+1)/2次，把所有点收缩到了一起。

 

1 #include 
      
        2 #include 
       
         3 #include 
        
          4 #include 
         
           5 #include 
          
            6  7 #define maxn 5050 8  9 struct edge10 {11     int v,next;12 };13 14 using namespace std;15 edge E[10010];16 int head[maxn];17 int n,m,tp,t,ans;18 int dfn[maxn],low[maxn];19 bool map[maxn][maxn];20 21 void add_edge(int u,int v)22 {23     E[tp].v=v;24     E[tp].next=head[u];25     head[u]=tp++;26 }27 28 void Tarjan(int u,int p)29 {30     dfn[u]=low[u]=++t;31     for(int i=head[u];i!=-1;i=E[i].next)32     {33         int v=E[i].v;34         35         if(!dfn[v])//如果为树边36         {37             Tarjan(v,u);38             low[u]=min(low[u],low[v]);39         }40         else if(v!=p)//不走回头路且为后向边41         {42             low[u]=min(low[u],dfn[v]);43         }44     }45     46 }47 48 void output()49 {50     int cnt[maxn],num=0;51     memset(cnt,0,sizeof(cnt));52     53     for(int i=1;i<=n;i++)54         for(int j=head[i];j!=-1;j=E[j].next)55         {56             int v=E[j].v;57             if(low[v]!=low[i])58                 cnt[low[i]]++; //求出每个点的度，当成有向图求。如果无向图则最后判断，度要除以259         }60     61     for(int i=0;i<=n;i++)62         if(cnt[i]==1)63             num++;64     printf("%d\n",(num+1)/2);65 }66 67 int main()68 {69     scanf("%d%d",&n,&m);70     memset(head,-1,sizeof(head));71     memset(map,false,sizeof(map));//记录重边72     memset(dfn,0,sizeof(dfn));//第一次访问。73     tp=t=0;74     75     int a,b;76     for(int i=0;i
          
         
        
       
      

 

 

 

自己的心得：

目前做的题目有：

  1.求一个无向图里面的桥个数，然后再添加边之后的桥的个数：具体做法就是先tarjan求出所有的桥和对应的low就是联通分量。

之后收缩联通块然后成为一棵树，然后就是对应输入边用并查集去搜，如果在同一联通块里面就没影响，如果在两联通块就合并联通块，每合并一次就减少一座桥。

2.求对应给出的无向图是否是三联通，先删除一个点然后求出有无割点，有则不是三联通。

3.构造双联通分量，用1的知识然后就出收缩数的叶子节点个数，最后(leaf+1)/2求出至少需要添加多少边构成双联通。

4.求出点联通分量的个数，求出桥联通分量的个数。