POJ 1144 Network【割顶】

学习的这一篇:https://www.byvoid.com/blog/biconnect

割顶:对于无向图G,如果删除某个点u后,连通分量数目增加,称u为图的关节点或者割顶

 

u为割顶的条件:

(1)u不为树根,以u的任一子节点为根的子树中没有一个点有返回u的祖先的反向边(返祖边)

(2)u为树根,且u有多于一个子树

紫书上有证明

即为,祖先与每一棵子树之间都有返祖边的话(即,删除u点之后,以v为根的整棵子树都可以通过这条返祖边连回到f),该点不是割顶,如果祖先与它的其中一棵子树缺少返祖边的话,那么这个点就是割顶

实现过程

(1)先链式前向星建图

(2)dfs

(3)定义dfn(u)为u在搜索中遍历到的序号      定义low(u)为u或u的子树能通过非父子边追溯到的最早的节点

  low(u)=min{dfn(u),       

                       dfn(v)//(u,v)为返祖边,等价于dfn(v)<dfn(u),且v不是u的父亲节点    

                       low(v)//(u,v)为树枝边(父子边)}

(4)当dfn(u)<=low(v)的时候,u为割顶

代码学习的这一篇

http://www.cnblogs.com/naturepengchen/articles/4053890.html

技术分享
 1 #include<iostream>  
 2 #include<cstdio>  
 3 #include<cstring> 
 4 #include <cmath> 
 5 #include<stack>
 6 #include<vector>
 7 #include<map> 
 8 #include<set>
 9 #include<queue> 
10 #include<algorithm>  
11 using namespace std;
12 
13 #define foreach(i,c) for (__typeof(c.begin()) i = c.begin(); i != c.end(); ++i)
14 
15 typedef long long LL;
16 const int INF = (1<<30)-1;
17 const int mod=1000000007;
18 const int maxn=100005;
19 
20 int first[maxn],next[maxn],ver[maxn];
21 int ecnt,tot;
22 int low[maxn],iscut[maxn],dfn[maxn];
23 
24 void dfs(int p,int pre){
25     low[p]=dfn[p]=++tot;
26     int son=0;
27     
28     for(int i=first[p];i!=-1;i=next[i]){
29         int v=ver[i];
30         if(!dfn[v]){
31             ++son;
32             dfs(v,p);
33             low[p]=min(low[p],low[v]);
34             if(low[v]>=dfn[p]) iscut[p]=1;
35         }
36         
37         else if(dfn[v]<dfn[p]&&v!=pre) {//用返祖边更新low函数 
38             low[p]=min(low[p],dfn[v]);
39         }
40     }
41     if(pre<0&&son==1) iscut[p]=0;     
42 }
43 
44 void addedges(int u,int v){
45     next[++ecnt]=first[u];
46     ver[ecnt]=v;
47     first[u]=ecnt;
48 }
49 
50 void init(){
51     memset(low,0,sizeof(low));
52     memset(dfn,0,sizeof(dfn));
53     memset(iscut,0,sizeof(iscut));
54     memset(first,-1,sizeof(first));
55     
56     ecnt=0;tot=0;
57 }
58 
59 int main(){
60     int a,b,n;
61     char c;
62     while(scanf("%d",&n)!=EOF&&n){
63         init();
64         while(scanf("%d",&a)!=EOF&&a){
65             while(scanf("%d%c",&b,&c)!=EOF){
66                 addedges(a,b);
67                 addedges(b,a);
68                 if(c==\n) break;
69             }
70         }
71         dfs(1,-1);
72         int ans=0;
73         for(int i=1;i<=n;i++)
74         ans+=iscut[i];
75         
76         printf("%d\n",ans);
77     }
78     return 0;
79 }
View Code

 

郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。