Better man

改变性格 改变命运!

 

zoj 1268

终于遇见了一个水题了
起初没有考虑到森林的情况
 1 //0 0也是树
 2 //有且只有一个顶点入度为0,其它顶点入度必须为一
 3 #include<iostream>
 4 using namespace std;
 5 int in[100];
 6 int hash[1000];
 7 bool visit[1000];
 8 int main()
 9 {
10       int a,b,cas=1;
11       while(scanf("%d%d",&a,&b)&&a>=0&&b>=0)
12       {
13             memset(visit,0,sizeof(visit));
14             memset(hash,0,sizeof(hash));
15             memset(in,0,sizeof(in));
16             if(a==0&&b==0)
17             {
18                   printf("Case %d is a tree.\n",cas++);
19                   continue;
20             }
21             int m=1;
22             hash[++hash[0]]=a;
23             visit[a]=visit[b]=1;
24             hash[++hash[0]]=b;
25             in[b]++;
26             bool flag=0;
27             while(scanf("%d%d",&a,&b)&&a&&b)
28             {
29                   ++m;
30                   if(!visit[a])
31                         hash[++hash[0]]=a;
32                   if(!visit[b])
33                         hash[++hash[0]]=b;
34                   visit[a]=visit[b]=1;
35                   if(++in[b]>1)
36                   {
37                         flag=1;
38                         printf("Case %d is not a tree.\n",cas++);
39                   }
40             }
41             if(flag)continue;
42             else 
43             {
44                   if(hash[0]-1!=m)
45                   {
46                         printf("Case %d is not a tree.\n",cas++);
47                         continue;
48                   }
49                   int root;
50                   bool flag=1;
51                   for(int i=1;i<=hash[0];++i)
52                         if(in[hash[i]]==0)
53                         {
54                               flag=0;
55                               root=i;
56                               break;
57                         }
58                   if(flag)
59                   {
60                         printf("Case %d is not a tree.\n",cas++);
61                         continue;
62                   }
63                   for(int i=1;i<=hash[0];++i)
64                         if(i!=root&&in[hash[i]]!=1)
65                         {
66                               printf("Case %d is not a tree.\n",cas++);
67                               continue;
68                         }
69                   printf("Case %d is a tree.\n",cas++);
70             }
71       }
72       return 0;
73 }


posted on 2009-02-06 17:04 SHFACM 阅读(309) 评论(1)  编辑 收藏 引用

评论

# re: zoj 1268 2009-02-11 15:54 刘静

原来你这一阵子在作zoj啊  回复  更多评论   


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


导航

统计

常用链接

留言簿(2)

随笔档案

文章分类

文章档案

搜索

最新评论

阅读排行榜

评论排行榜