bon

  C++博客 :: 首页 :: 联系 :: 聚合  :: 管理
  46 Posts :: 0 Stories :: 12 Comments :: 0 Trackbacks

常用链接

留言簿(2)

我参与的团队

搜索

  •  

最新评论

阅读排行榜

评论排行榜

无向联通图的割顶 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 }



 

posted on 2008-03-27 16:12 bon 阅读(653) 评论(0)  编辑 收藏 引用

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


Google PageRank 
Checker - Page Rank Calculator