|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42 |
无向图连通图（割） int
bridge,edge[v][v],ans[v],prve[v],vis[v];// vis[i] 0为尚未访问 1为正在访问 2已经访问//ans[i] 该点能到达的最小序号// pre[i] 该点的序号// INIT: edge[][]邻接矩阵;vis[],pre[],anc[],deg[]置为0; //k=deg[0], deg[i]+1(i=1…n-1) 为删除该节点后得到的连通图个数 // 注意:0作为根比较特殊!void
dfs(int
cur,int
father,int
dep,int
n){ int
cnt = 0; vis[cur] = 1; pre[cur] = ans[cur] = dep; for(int
i=0;i<n;i++) { if(edge[cur][i])//有一条边cur到i { if(i!=father && 1 == vis[i]) { if(pre[i]<ans[cur]) { ans[cur] = pre[i];//是一条回边 } } } if(0==vis[i]) //是一条树边 { dfs(i,cur,dep+1,n); ++cnt if(ans[i]<ans[cur]) ans[cur]= ans[i];//更新该点能到达的最小值 if((cur==0 && cnt>1)//父节点并且分支个数大于1 || (cnt!=0 && ans[i]>=pre[cur]) ++deg[cur]; } } vis[cur] =2;} |
原文：http://www.cnblogs.com/Deng1185246160/p/3580936.html