poj1308

http://poj.org/problem?id=1308

题目要求是判断是不是为一棵树

主要看是否满足2个条件

共有n个不同的数也就是n个节点

1 有n-1个入度去除根节点一个节点只有一个入度

2 不能有环就是单方向的

其实只要判断条件1就可以了只要是环肯定不会为n-1个入度所以只判断第一个条件就好

代码如下用a[]判断节点的入度是否唯一用K来计算总入度是否为n-1

用b[]来判断n的值为几

这个题还要注意一点 0 0是空树也是树

View Code

 1 #include <stdio.h>
 2 #include<string.h>
 3 int main()
 4 {
 5     int a[30000] = {0}, i = 0, j, k, flag,x,y,b[30000];
 6     while(scanf("%d%d", &x, &y)!=EOF)
 7     {
 8         k = 0;
 9         j = 0;
10         i++;
11         flag = 1;
12         memset(a, 0, sizeof(a));
13         memset(b,0,sizeof(b)) ;
14         if(x<0&&y<0)
15         break;
16         a[y] = x;
17         k++;
18         j++;
19         b[y] = 1;
20         if(b[x]!=1)
21         {
22             b[x] = 1;
23             j++;
24         }
25         if(x ==0&&y ==0)
26         printf("Case %d is a tree.\n", i);
27         else
28         {
29             while(scanf("%d%d", &x, &y), x!=0&&y!=0)
30             {
31                 if(b[x]!=1)
32                 {
33                     b[x] = 1;
34                     j++;
35                 }
36                 if(b[y]!=1)
37                 {
38                     b[y] = 1;
39                     j++;
40                 }
41                 if(a[y] == 0)
42                 {
43                     a[y] = x;
44                     k++;
45                 }
46                 else
47                 {
48                     flag = 0;
49                 }
50             }
51             if(k == j-1&&flag!=0)
52             printf("Case %d is a tree.\n", i);
53             else
54             printf("Case %d is not a tree.\n", i);
55         }
56     }
57     return 0;
58 }