Better man

改变性格 改变命运!

 

求割顶(poj1144)

 1 #include<iostream>
 2 using namespace std;
 3 #define black 2
 4 #define white 0
 5 #define gray 1
 6 bool map[101][101];
 7 int n;//表示节点个数
 8 int color[101],D[101];
 9 int root=1;//头节点
10 int ancestor[101];
11 int cnt;
12 int tme=0;
13 int A[101];
14 bool cut[101];
15 void dfs(int k,int father,int dep)
16 {
17       int tot;
18       color[k]=gray;
19       D[k]=dep;
20       ancestor[k]=dep;
21       tot=0;//表示顶点k的儿子的数量
22       for(int i=1;i<=n;++i)
23       {
24             if(map[i][k]&&i!=father&&color[i]==gray)
25                   ancestor[k]=min(ancestor[k],D[i]);
26             if(map[i][k]&&color[i]==white)
27             {
28                   dfs(i,k,dep+1);
29                   tot++;
30                   ancestor[k]=min(ancestor[k],ancestor[i]);
31                   //根节点
32                   if(k==root&&tot>1)cut[k]=1;
33                   if(k!=root&&ancestor[i]>=D[k])
34                         cut[k]=1;
35             }
36       }
37       color[k]=black;
38       A[k]=++tme;//时间戳
39 }
40 int main()
41 {
42       int t1,t3;
43       char t2;
44       while(scanf("%d",&n)&&n)
45       {
46             cnt=0;
47             memset(map,0,sizeof(map));
48             memset(cut,0,sizeof(cut));
49             memset(ancestor,0,sizeof(ancestor));
50             memset(color,0,sizeof(color));
51             memset(D,0,sizeof(D));
52             while(scanf("%d",&t1)&&t1)
53             {
54                   while((t2=getchar())!='\n')
55                   {
56                         scanf("%d",&t3);
57                         map[t1][t3]=map[t3][t1]=1;
58                   }
59             }
60             dfs(1,0,1);
61             for(int i=1;i<=n;++i)
62                   if(cut[i])cnt++;
63             printf("%d\n",cnt);
64       }
65       return 0;
66 }
67 

posted on 2009-01-27 17:50 SHFACM 阅读(482) 评论(1)  编辑 收藏 引用

评论

# re: 求割顶(poj1144) 2009-05-19 17:32 shishuai

你缺少个 min函数定义!能加上吗?  回复  更多评论   


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


导航

统计

常用链接

留言簿(2)

随笔档案

文章分类

文章档案

搜索

最新评论

阅读排行榜

评论排行榜