|
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 |
无向图找桥 int
bridge,edge[v][v],ans[v],prve[v],vis[v];// vis[i] 0为尚未访问 1为正在访问 2已经访问//ans[i] 该点能到达的最小序号// pre[i] 该点的序号void
dfs(int
cur,int
father,int
dep,int
n){ if(bridge) // 已经找到桥 return
; 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); if(bridge) return
; if(ans[i]<ans[cur]) ans[cur]= ans[i];//更新该点能到达的最小值 if(ans[i]>pre[cur]) { bridge = 1; return
; } } } vis[cur] =2;} |
原文：http://www.cnblogs.com/Deng1185246160/p/3580923.html