首页 > 代码库 > 双连通问题
双连通问题
一些定义：
割点集合（割集）：在一个无向连通图中，如果有一个顶点集合，删除这个顶点集合，以及这个集合中所有顶点相关联的边以后，原图变成多个连通块，就称这个点集为割点集合。
点连通度：最小割点集合中的顶点数。
割边集合：如果有一个边集合，删除这个边集合以后，原图变成多个连通块，就称这个点集为割边集合。
边连通度：最小割边集合中的边数。
点双连通：如果一个无向连通图的点连通度大于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]<low[v]) //判断桥的条件27 {28 bridge++;29 edge[i].iscut=1;30 edge[i^1].iscut=1;31 }32 if(u!=from&&low[v]>=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<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 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<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<vector> 5 #include<algorithm> 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]<low[v]) //判断桥的条件 32 { 33 bridge++; 34 edge[i].iscut=1; 35 edge[i^1].iscut=1; 36 } 37 if(u!=from&&low[v]>=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<pair<int,int> >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<res.size();i++)105 printf("%d - %d\n",res[i].first-1,res[i].second-1);106 printf("\n");107 }108 return 0;109 }
poj3177 Redundant Paths
题意：就是给了一个连通图，问加多少条边可以变成边双连通。
详细题解：http://blog.csdn.net/wangjian8006/article/details/7990666
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<vector> 5 #include<algorithm> 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]<low[v]) //判断桥的条件34 {35 bridge++;36 edge[i].iscut=1;37 edge[i^1].iscut=1;38 }39 }40 else if(insta[v]) low[u]=min(low[u],low[v]);41 }42 if(low[u]==dfn[u])43 {44 block++;45 do46 {47 v=sta[--top];48 insta[v]=0;49 belg[v]=block;50 }51 while(v!=u) ;52 }53 }54 void tarjan(int n)55 {56 memset(insta,0,sizeof(insta));57 memset(add_block,0,sizeof(add_block));58 memset(dfn,0,sizeof(dfn));59 memset(cut,0,sizeof(cut));60 sig=top=0; bridge=0;61 tarjanbfs(1,1);62 }63 void addedge(int i,int j)64 {65 edge[tot].to=j;edge[tot].next=head[i];66 edge[tot].iscut=0;head[i]=tot++;67 }68 void init()69 {70 memset(head,-1,sizeof(head));71 tot=0;72 }73 int main()74 {75 //freopen("test.txt","r",stdin);76 int n,m,i,j,k,t,ans;77 while(scanf("%d%d",&n,&m)!=EOF)78 {79 init();80 while(m--)81 {82 scanf("%d%d)",&i,&j);83 addedge(i,j);84 addedge(j,i);85 }86 tarjan(n);87 memset(de,0,sizeof(de));88 ans=0;89 for(i=1;i<=n;i++)90 for(k=head[i];k!=-1;k=edge[k].next)91 if(edge[k].iscut) de[belg[i]] ++;92 for(i=1;i<=block;i++)93 if(de[i]==1) ans++;94 printf("%d\n",(ans+1)/2);95 }96 return 0;97 }
POJ 3694 Network
题意：给出一幅无向图，问在加入新边的过程中桥的数目的变化。
PS:LCA太烦了，我试着去做此题。然后放弃了。
PS：双连通的题目一般不出现，出现了就基本上没多少队伍做得出来。
双连通问题
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。