一些定义：

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

点连通度：最小割点集合中的顶点数。

割边集合：如果有一个边集合，删除这个边集合以后，原图变成多个连通块，就称这个点集为割边集合。

边连通度：最小割边集合中的边数。

点双连通：如果一个无向连通图的点连通度大于1，则称该图是点双连通的，简称双连通或重连通。

割点：一个图有割点，当且仅当这个图的点连通度为1，则割点集合的唯一元素被称为割点，又叫关节点。

边双连通：如果一个无向连通图的边连通度大于1，则称该图是边双连通的，简称双连通或重连通。

割边（桥）：一个图有桥，当且仅当这个图的边连通度为1，则割边集合的唯一元素被称为桥，又叫关节边。

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

求割点与桥：

该算法是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)。

下面的是求割边与割点的模版：

1 const int N =1010, M=100010; 2 struct Edge 3 { 4     int to, next; 5     bool iscut; 6 }edge[M]; 7 int head[N],tot, low[N], dfn[N], sta[N]; 8 int add_block[N];//删除一个点以后增加的连通块 9 bool insta[N],cut[N];10 int top,sig,bridge,child;11 void tarjanbfs(int u, int from)12 {13     sta[top++]=u;14     dfn[u]=++sig; low[u]=sig;15     insta[u]=1;16     child=0;17     for(int i=head[u];i!=-1;i=edge[i].next)18     {19         int v=edge[i].to;20         if(v ==from) continue;21         if(!dfn[v])22         {23             child++;24             tarjanbfs(v,u);25             low[u]=min(low[u],low[v]);26             if(dfn[u]
      
       =dfn[u]) // 割点33             {34                 cut[u]=1;35                 add_block[u]++;36             }37         }38         else low[u]=min(low[u],low[v]);39     }40     if(u==from && child>1) cut[u]=1; //这也是割点41     if(u==from) add_block[u]=child -1;42     insta[u]=0;43     top--;44 }45 void tarjan(int n)46 {47     memset(insta,0,sizeof(insta));48     memset(add_block,0,sizeof(add_block));49     memset(dfn,0,sizeof(dfn));50     memset(cut,0,sizeof(cut));51     sig=top=0; bridge=0;52     for(int i=1;i<=n;i++)53         if(!dfn[i]) tarjanbfs(i,i);54 }55 void addedge(int i,int j)56 {57     edge[tot].to=j;edge[tot].next=head[i];58     edge[tot].iscut=0;head[i]=tot++;59 }60 void init()61 {62     memset(head,-1,sizeof(head));63     tot=0;64 }
      

 

一些题目：

hdu4587  TWO NODES

题意：求任意删除两个点以后，可以得到的最多的连通分支数。

枚举删除一条边后产生的割点，求删除该割点（或许有多个割点）产生的连通分支数。

1 #include
      
        2 #include
       
         3 #include
        
          4 #include
         
           5 using namespace std; 6  7 const int N =5010, M=10010; 8 struct Edge 9 {10     int to, next;11 }edge[M];12 int head[N],tot, low[N], dfn[N], sta[N];13 int add_block[N];//删除一个点以后增加的连通块14 bool insta[N],cut[N];15 int top,sig,cnt,tt,ans;16 void tarjanbfs(int u, int from)17 {18     sta[top++]=u;19     dfn[u]=++sig; low[u]=sig;20     insta[u]=1;21     int child=0;22     for(int i=head[u];i!=-1;i=edge[i].next)23     {24         int v=edge[i].to;25         if(v ==from) continue;26         if(v ==tt) continue;27         if(!dfn[v])28         {29             child++;30             tarjanbfs(v,u);31             low[u]=min(low[u],low[v]);32             if(u!=from&&low[v]>=dfn[u]) // 割点33             {34                 cut[u]=1;35                 add_block[u]++;36             }37         }38         else if(insta[v]) low[u]=min(low[u],dfn[v]);39     }40     if(u==from && child>1) cut[u]=1; //这也是割点41     if(u==from) add_block[u]=child -1;42     insta[u]=0;43     top--;44 }45 void tarjan(int n)46 {47     memset(insta,0,sizeof(insta));48     memset(add_block,0,sizeof(add_block));49     memset(dfn,0,sizeof(dfn));50     memset(cut,0,sizeof(cut));51     sig=top=0;52     ans=cnt=0;53     for(int i=1;i<=n;i++)54         if(i!=tt&&!dfn[i])55         {56             tarjanbfs(i,i);57             cnt++;58         }59     for(int i=1;i<=n;i++)60         if(i!=tt)61         {62             ans=max(ans,cnt+add_block[i]);63         }64 }65 void addedge(int i,int j)66 {67     edge[tot].to=j;edge[tot].next=head[i];head[i]=tot++;68 }69 void init()70 {71     memset(head,-1,sizeof(head));72     tot=0;73 }74 75 int main()76 {77     //freopen("test.txt","r",stdin);78     int n,m,i,j,k;79     while(scanf("%d%d",&n,&m)!=EOF)80     {81         init();82         while(m--)83         {84             scanf("%d%d",&i,&j);85             i++;j++;86             addedge(i,j);87             addedge(j,i);88         }89         int s=0;90         for(i=1;i<=n;i++)91         {92             tt=i;93             tarjan(n);94             s=max(s,ans);95         }96         printf("%d\n",s);97     }98     return 0;99 }
         
        
       
      

 

UVA 796 Critical Links

题意：给出一幅无向图，求出割边的数目，以及输出割边（输出有顺序）。

1 #include
      
         2 #include
       
          3 #include
        
           4 #include
         
            5 #include
          
             6 using namespace std;  7 const int N =1010, M=100010;  8 struct Edge  9 { 10     int to, next; 11     bool iscut; 12 }edge[M]; 13 int head[N],tot, low[N], dfn[N], sta[N]; 14 int add_block[N];//删除一个点以后增加的连通块 15 bool insta[N],cut[N]; 16 int top,sig,bridge,child; 17 void tarjanbfs(int u, int from) 18 { 19     sta[top++]=u; 20     dfn[u]=++sig; low[u]=sig; 21     insta[u]=1; 22     for(int i=head[u];i!=-1;i=edge[i].next) 23     { 24         int v=edge[i].to; 25         if(v ==from) continue; 26         if(!dfn[v]) 27         { 28             child++; 29             tarjanbfs(v,u); 30             low[u]=min(low[u],low[v]); 31             if(dfn[u]
           
            =dfn[u]) // 割点 38 { 39 cut[u]=1; 40 add_block[u]++; 41 } 42 } 43 else low[u]=min(low[u],low[v]); 44 } 45 if(u==from && child>1) cut[u]=1; //这也是割点 46 if(u==from) add_block[u]=child -1; 47 insta[u]=0; 48 top--; 49 } 50 void tarjan(int n) 51 { 52 memset(insta,0,sizeof(insta)); 53 memset(add_block,0,sizeof(add_block)); 54 memset(dfn,0,sizeof(dfn)); 55 memset(cut,0,sizeof(cut)); 56 sig=top=0; bridge=0; 57 for(int i=1;i<=n;i++) 58 if(!dfn[i]) tarjanbfs(i,i); 59 } 60 void addedge(int i,int j) 61 { 62 edge[tot].to=j;edge[tot].next=head[i]; 63 edge[tot].iscut=0;head[i]=tot++; 64 } 65 void init() 66 { 67 memset(head,-1,sizeof(head)); 68 tot=0; 69 } 70 vector
            
             
               >res; 71 int main() 72 { 73 //freopen("test.txt","r",stdin); 74 int n,i,j,k,t; 75 char ch; 76 while(scanf("%d",&n)!=EOF) 77 { 78 init(); 79 res.clear(); 80 for(t=1;t<=n;t++) 81 { 82 83 scanf("%d (%d)",&i,&k); 84 i++; 85 while(k--){ 86 scanf("%d",&j); 87 j++; 88 if(j<=i) continue; 89 addedge(i,j); 90 addedge(j,i); 91 } 92 } 93 tarjan(n); 94 printf("%d critical links\n",bridge); 95 for(i=1;i<=n;i++) 96 { 97 for(k=head[i];k!=-1;k=edge[k].next) 98 { 99 if(edge[k].iscut&&edge[k].to>i)100 res.push_back(make_pair(i,edge[k].to));101 }102 }103 sort(res.begin(),res.end());104 for(i=0;i
             
            
           
          
         
        
       
      

 

poj3177　　Redundant Paths

双连通构造问题，比较热的题目

题意：就是给了一个连通图，问加多少条边可以变成边双连通。

详细题解：

1 #include
      
        2 #include
       
         3 #include
        
          4 #include
         
           5 #include
          
            6 using namespace std; 7  8 const int N =5010, M=100010; 9 struct Edge10 {11     int to, next;12     bool iscut;13 }edge[M];14 int head[N],tot, low[N], dfn[N], sta[N], belg[N];15 int add_block[N];//删除一个点以后增加的连通块16 bool insta[N],cut[N];17 int top,sig,bridge,block;//边连通块数18 int de[N];//度数19 void tarjanbfs(int u, int from)20 {21     int v;22     sta[top++]=u;23     dfn[u]=++sig; low[u]=sig;24     insta[u]=1;25     for(int i=head[u];i!=-1;i=edge[i].next)26     {27         v=edge[i].to;28         if(v ==from) continue;29         if(!dfn[v])30         {31             tarjanbfs(v,u);32             low[u]=min(low[u],low[v]);33             if(dfn[u]
          
         
        
       
      

 

 POJ 3694 Network

题意：给出一幅无向图，问在加入新边的过程中桥的数目的变化。

PS:LCA太烦了，我试着去做此题。然后放弃了。

 

PS：双连通的题目一般不出现，出现了就基本上没多少队伍做得出来。