pre[i]为在深搜过程中i被遍历到的顺序序号 low[i] 为i及其后代能连到的最早的祖先
只要u有一个 子结点v存在low[v]>=pre[u]则u是割点 ( 即： v及其后代连不到比u更早的祖先)。
而特殊的 要是low[v]>pre[u] 那么(u,v) 就是桥。因为在算法过程中这条件不止成立一次 所以不能一遇到这给条件就输出 割点或桥
贴个模板先：
1 #include<iostream>
2 #include<vector>
3 #include<string.h>
4 using namespace std;
5 vector < int > g[1002];
6 int pre[1002],low[1002],iscut[1002],c,vis[1002],hash[1002][1002];
7
8 int dfs(int u,int p)
9 {
10 int lowu,lowv,child=0;
11 lowu=pre[u]=c++;
12 for(int i=0;i<g[u].size();i++)
13 {
14
15 int v=g[u][i];
16 if(!pre[v])
17 {
18 child++;
19 lowv=dfs(v,u); // 子节点的 能连回的最早 祖先节点
20 if(lowv<lowu)
21 lowu=lowv;
22 if(lowv>=pre[u]) // 自己能连回的最早祖先节点
23 iscut[u]=1;
24 }
25 else if(v!=p&&pre[v]<lowu)
26 lowu=pre[v];
27 if(p<0&&child==1)
28 iscut[u]=0;
29 }
30 low[u]=lowu;
31 return lowu;
32 }
c 在主函数中初始化为 1
（一） 割点
poj 1144 http://poj.org/problem?id=1144 （模板题）
题意：求一个图中有多少个割点 代码就不贴了
poj 1523 SPF http://poj.org/problem?id=1523
题意：给定一个连通网络，网络的结点数<=1000，求出这个网络的所有割点编号，并求出若删去其中一个割点k后，对应的，原网络会被分割为多少个连通分量？
求删除一个割点i后的连通分支数不必在图中把和点i相关联的边都去掉 照完再补回来 只要 从i的相邻点一个个开始dfs 而不是从点i dfs 就可以了**
1 #include<iostream>
2 #include<vector>
3 #include<string.h>
4 using namespace std;
5 vector < int > g[1002];
6 int pre[1002],low[1002],iscut[1002],c,vis[1002],hash[1002][1002];
7
8 int dfs(int u,int p)
9 {
10 int lowu,lowv,child=0;
11 lowu=pre[u]=c++;
12 for(int i=0;i<g[u].size();i++)
13 {
14
15 int v=g[u][i];
16 if(!pre[v])
17 {
18 child++;
19 lowv=dfs(v,u); // 子节点的 能连回的最早 祖先节点
20 if(lowv<lowu)
21 lowu=lowv;
22 if(lowv>=pre[u]) // 自己能连回的最早祖先节点
23 iscut[u]=1;
24 }
25 else if(v!=p&&pre[v]<lowu)
26 lowu=pre[v];
27 if(p<0&&child==1)
28 iscut[u]=0;
29 }
30 low[u]=lowu;
31 return lowu;
32 }
33
34 void dfs2(int n,int p) //找连通分支数
35 {
36 vis[n]=1;
37 for(int i=0;i<g[n].size ();i++)
38 {
39 int v; v=g[n][i];
40 if(v!=p&&!vis[v])
41 dfs2(v,p);
42 }
43 }
44 int main()
45 {
46 int i,j,m,n,u,v,start,ww=1;
47 while(1)
48 {
49 int temp=0;
50 memset(hash,0,sizeof(hash));
51 while(scanf("%d",&u))
52 {
53 if(u==0)
54 break;
55 scanf("%d",&v);
56 if(!hash[u][v]&&!hash[v][u])
57 {
58 g[u].push_back (v);
59 g[v].push_back (u);
60 temp++;
61 hash[u][v]=1;
62 hash[v][u]=1;
63 }
64 }
65 if(temp==0)
66 break;
67 printf("Network #%dn",ww++);
68 memset(pre,0,sizeof(pre));
69 memset(iscut,0,sizeof(iscut));
70 for(i=1;i<=1000;i++)
71 if(!pre[i]&&g[i].size ()>0)
72 {
73 c=1;
74 dfs(i,-1);
75 }
76 int flag=0; //是不是 有割点
77 for(i=1;i<=1000;i++)
78 {
79
80 if(iscut[i])// 若i是割点 找没有了点i 整个图的连通分支数
81 {
82 memset(vis,0,sizeof(vis));
83 flag=1;
84 int temp=0; //去掉 i点的 连通分支数
85 for(j=0;j<g[i].size ();j++)
86 if(!vis[g[i][j]])
87 {
88 temp++;
89 dfs2(g[i][j],i);
90 }
91 printf(" SPF node %d leaves %d subnetsn",i,temp);
92 }
93 }
94 if(flag==0)
95 printf(" No SPF nodesn");
96 printf("n");
97 for(i=0;i<=1000;i++)
98 g[i].clear ();
99
100 }
101 return 0;
102 }
View Code
poj 2117Electricity http://poj.org/problem?id=2117
题意：一个无向图，现在要去掉其中一个点，要求去掉这个点之后，总连通分支数最大
和上题差不多
1 #include<iostream>
2 #include<vector>
3 #include<string.h>
4 using namespace std;
5 vector < int > g[10002];
6 int pre[10002],count1,low[100022],iscut[10002],c,vis[10002];
7 int dfs(int u,int p)
8 {
9 int lowu,lowv,child=0;
10 lowu=pre[u]=c++;
11 for(int i=0;i<g[u].size();i++)
12 {
13 int v=g[u][i];
14 if(!pre[v])
15 {
16 child++;
17 lowv=dfs(v,u); // 子节点的 能连回的最早 祖先节点
18 if(lowv<lowu)
19 lowu=lowv;
20 if(lowv>=pre[u]) // 自己能连回的最早祖先节点
21 iscut[u]=1;
22 }
23 else if(v!=p&&pre[v]<lowu)
24 lowu=pre[v];
25 if(p<0&&child==1)
26 iscut[u]=0;
27 }
28 low[u]=lowu;
29 return lowu;
30 }
31
32 void dfs2(int n,int p)
33 {
34 vis[n]=1;
35 for(int i=0;i<g[n].size ();i++)
36 {
37 int v; v=g[n][i];
38 if(v!=p&&!vis[v])
39 dfs2(v,p);
40 }
41 }
42
43
44 int main()
45 {
46 int i,j,m,n,u,v;
47 while(scanf("%d%d",&n,&m))
48 {
49 if(n==0&&m==0)
50 break;
51 if(m==0)
52 {
53 printf("%dn",n-1);
54 continue;
55 }
56 while(m--)
57 {
58 scanf("%d%d",&u,&v);
59 g[u].push_back(v);
60 g[v].push_back(u);
61 }
62 memset(pre,0,sizeof(pre));
63 memset(iscut,0,sizeof(iscut));
64 count1=0 ; // l连通分支数
65 for(i=0;i<n;i++)
66 if(!pre[i])
67 {
68 c=1; //一开始c=0; wa
69 count1++;
70 dfs(i,-1);
71 }
72 int ans; ans=count1;
73 for(i=0;i<n;i++)
74 {
75 if(iscut[i])
76 {
77 memset(vis,0,sizeof(vis));
78 int temp=0;
79 for(j=0;j<g[i].size ();j++)
80 if(!vis[g[i][j]])
81 {
82 temp++;
83 dfs2(g[i][j],i);
84 }
85 if(temp-1+count1>ans)
86 ans=temp-1+count1;
87 }
88 }
89 printf("%dn",ans);
90 for(i=0;i<=n;i++)
91 g[i].clear ();
92 }
93 return 0;
94 }
View Code
（二）桥
hdu
1 #include<iostream>
2 #include<stdio.h>
3 #include<string.h>
4 #include<vector>
5 using namespace std;
6 #define INF 10000000
7 int w[1002][1002],cc,uu[10002],vv[10002],pre[1002],low[1002],num,vis[1002],ww[1002][1002],pp;
8 vector <int > g[1002];
9
10 int dfs(int u,int fa)
11 {
12 int i,child=0;
13 low[u]=pre[u]=num++;
14 int len=g[u].size ();
15 for(i=0;i<len;i++)
16 {
17 int v=g[u][i];
18 if(!pre[v])
19 {
20 int lowv=dfs(v,u);
21 if(low[u]>lowv)
22 low[u]=lowv;
23 if(lowv>pre[u])
24 {
25 if(ww[u][v]==1)
26 { uu[cc]=u; vv[cc++]=v;}
27 }
28 }
29 else if(pre[v]<pre[u]&&pre[v]<low[u]&&v!=fa)
30 low[u]=pre[v];
31 }
32 return low[u];
33 }
34
35 void dfs1(int x)
36 {
37 vis[x]=pp;
38 for(int i=0;i<g[x].size ();i++)
39 if(!vis[g[x][i]])
40 dfs1(g[x][i]);
41 }
42
43
44 int main()
45 {
46 int i,n,m,a,b,c,t=0;
47 while(scanf("%d%d",&n,&m))
48 {
49 t++;if(t>12) break;
50 if(n==0&&m==0)
51 break;
52 memset(w,-1,sizeof(w));
53 memset(ww,0,sizeof(ww));
54 while(m--)
55 {
56 scanf("%d%d%d",&a,&b,&c);
57 w[a][b]=c;
58 ww[a][b]++;
59 ww[b][a]++;
60 g[a].push_back(b);
61 g[b].push_back(a);
62 }
63 pp=1; num=1; cc=0;
64 memset(vis,0,sizeof(vis));
65 memset(pre,0,sizeof(pre));
66
67 for(i=1;i<=n;i++)
68 {
69 if(!vis[i])
70 {
71 dfs1(i);
72 pp++;
73
74 }
75 }
76 if(pp>2)
77 {
78 printf("0n");
79 continue;
80 }
81 dfs(1,-1);
82 int ans=INF;
83 for(i=0;i<cc;i++)
84 {
85 //printf("---%d %dn",uu[i],vv[i]);
86 if(w[uu[i]][vv[i]]<ans)
87 ans=w[uu[i]][vv[i]];
88 }
89 if(ans==0)
90 ans=1;
91
92 if(cc==0)
93 printf("-1n");
94 else
95 printf("%dn",ans);
96 for(i=0;i<=n;i++)
97 g[i].clear ();
98
99 }
100 return 0;
101 }
View Code
原文链接: https://www.cnblogs.com/assult/p/3209883.html
欢迎关注
微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍
原创文章受到原创版权保护。转载请注明出处：https://www.ccppcoding.com/archives/97137
非原创文章文中已经注明原地址，如有侵权，联系删除
关注公众号【高性能架构探索】，第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处！
