無向聯(lián)通圖的割頂 i 是指：若在圖的dfs樹上，i 存在兒子節(jié)點(diǎn) s ，使得 s 及 s 的所有子孫的后向邊不指向 i 的祖先（可以指向i）
無向聯(lián)通圖的橋 (i,j) 是指：刪除了 (i,j) 后點(diǎn)i 與j 不再聯(lián)通。
下面的程序用color來表示訪問的順序：color[i]==-1表示未訪問過，color[i]==0表示正在訪問i及i的子孫，color[i]==1表示i的子孫都訪問完了。這個量用于判斷邊 (i,j) 是否為后向邊。當(dāng)color[i]==0 且 color[j]==0時，說明 i 是 j 在dfs樹上的后代，因?yàn)樵L問到 i 時 j 的所有子孫還沒有完全訪問完，因此 i 是 j 的一個后代。
ancestor[i] 表示i及i的所有子孫的后向邊最遠(yuǎn)能指到哪個祖先，如：ancestor[i]=1表示i及i的子孫，這些點(diǎn)的后向邊最遠(yuǎn)指到深度為1的祖先（注意到dfs樹是有層次的）。
1 // 無向圖聯(lián)通的dfs，同時包括找割點(diǎn)與橋
2
3 #include <iostream>
4 #define min(a,b) (a<b?a:b)
5 using namespace std;
6
7 const int maxn=10;
8 int G[maxn][maxn];
9 int bridge[maxn][maxn]; // 記錄(i,j)是否為橋
10 int color[maxn]; // 用于找后向邊
11 int ancestor[maxn]; // 記錄點(diǎn)i及i的子孫的后向邊最后能指到哪
12 int deep[maxn]; // 點(diǎn)i在dfs樹上的深度
13 int total[maxn]; // 點(diǎn)i子孫個數(shù)
14 int cut[maxn]; // 標(biāo)記是否為割頂
15 int root; // 根節(jié)點(diǎn)編號
16 int n,e; // 點(diǎn)數(shù)及邊數(shù)
17 //int timestamp; // 時間戳
18
19 void dfs(int k,int father,int d)
20 {// 當(dāng)前點(diǎn)k，k的父親，k的深度
21 deep[k]=d;
22 ancestor[k]=d;
23 color[k]=0; // 灰色
24 for(int i=0;i<maxn;i++){
25 // 先判斷k本身的后向邊
26 if(G[k][i] && i!=father && color[i]==0) ancestor[k]=min(ancestor[k],deep[i]);
27 // 對k的兒子dfs
28 if(G[k][i] && color[i]==-1){dfs(i,k,d+1);
29 total[k]++;
30 // k的(兒子及該兒子的子孫所能向后指的深度的最小值ancestor[i])
31 ancestor[k]=min(ancestor[k],ancestor[i]);
32 if((k==root && total[k]>1) || (k!=root && ancestor[i]>=deep[k])) cut[k]=1;
33 if(ancestor[i]>deep[k]) bridge[i][k]=bridge[k][i]=1;
34 }
35 }
36 color[k]=1; //黑色
37 }
38
39 int main()
40 {
41 freopen("graph.txt","r",stdin);
42 int i,j,k;
43 scanf("%d%d",&n,&e);
44 memset(G,0,sizeof(G));
45 for(i=0;i<e;i++){
46 scanf("%d%d",&j,&k);
47 G[j-1][k-1]=G[k-1][j-1]=1;
48 }
49 memset(cut,0,sizeof(cut));
50 memset(bridge,0,sizeof(bridge));
51 memset(color,-1,sizeof(color));
52 root=0;
53 ancestor[0]=deep[0]=1;
54 color[0]=0;
55 for(i=0;i<n;i++) if(G[root][i]) dfs(i,root,2);
56 printf("cuts:\n");
57 for(i=0;i<n;i++) if(cut[i]) printf("%d ",i);
58 printf("\nbridges:\n");
59 for(i=0;i<n;i++) for(j=i+1;j<n;j++) if(bridge[i][j]) printf("%d %d\n",i,j);
60 return 1;
61 }