无向联通图的割顶 i 是指：若在图的dfs树上，i 存在儿子节点 s ，使得 s 及 s 的所有子孙的后向边不指向 i 的祖先（可以指向i）
无向联通图的桥 (i,j) 是指：删除了 (i,j) 后点i 与j 不再联通。
下面的程序用color来表示访问的顺序：color[i]==-1表示未访问过，color[i]==0表示正在访问i及i的子孙，color[i]==1表示i的子孙都访问完了。这个量用于判断边 (i,j) 是否为后向边。当color[i]==0 且 color[j]==0时，说明 i 是 j 在dfs树上的后代，因为访问到 i 时 j 的所有子孙还没有完全访问完，因此 i 是 j 的一个后代。
ancestor[i] 表示i及i的所有子孙的后向边最远能指到哪个祖先，如：ancestor[i]=1表示i及i的子孙，这些点的后向边最远指到深度为1的祖先（注意到dfs树是有层次的）。
1 // 无向图联通的dfs，同时包括找割点与桥
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]; // 记录点i及i的子孙的后向边最后能指到哪
12 int deep[maxn]; // 点i在dfs树上的深度
13 int total[maxn]; // 点i子孙个数
14 int cut[maxn]; // 标记是否为割顶
15 int root; // 根节点编号
16 int n,e; // 点数及边数
17 //int timestamp; // 时间戳
18
19 void dfs(int k,int father,int d)
20 {// 当前点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 }