hdu 1325 is it a tree?

网上一搜全是并查集。。并查集POJ可以水过，HDU就不行了。。

并查集的话：

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 using namespace std;
 5 int pre[1005];
 6 bool vis[1005];
 7 int num[1005];
 8 bool flag;
 9 int x,y,icase=1;
10 void init()
11 {
12     for(int i=0;i<=1000;i++)
13         pre[i]=i;
14     memset(num,0,sizeof(num));
15     memset(vis,false,sizeof(vis));
16     flag=false;
17 }
18 int find(int x)
19 {
20     if(pre[x]!=x)
21         pre[x]=find(pre[x]);
22     return pre[x];
23 }
24 void judge()
25 {
26     for(int i=1;i<=1000;i++)
27         if(vis[i]) num[find(i)]++;
28     int key=0;
29     for(int i=1;i<=1000;i++)
30         if(num[i]>1) key++;
31     if(key>1) flag=true;
32 }
33 int main()
34 {
35 //    freopen("in.txt","r",stdin);
36     init();
37     while(1)
38     {
39         scanf("%d%d",&x,&y);
40         if(x<0 && y<0)
41             break;
42         else if(x==0 && y==0)
43         {
44             judge();
45             if(flag)
46                 printf("Case %d is not a tree.
",icase++);
47             else
48                 printf("Case %d is a tree.
",icase++);
49             init();
50             continue;
51         }
52         else
53         {
54             vis[x]=vis[y]=true;
55             if(find(x)==find(y) || pre[y]!=y)
56                 flag=true;
57             else
58                 pre[y]=x;
59         }
60     }
61     return 0;
62 }

迪哥代码

有个坑是只要是输入两个负数就结束，不一定是-1 -1

判断图是否为树：1.是否为连通图 2.是否有环

因为题目给的是从父亲指向儿子，所以直接判断点的入度就可以了

 1 #include "iostream"
 2 #include "memory.h"
 3 #include "cstdio"
 4 using namespace std;
 5 #define MAXN 1111
 6 int fa[MAXN];
 7 int in_degree[MAXN];
 8 bool c[MAXN];
 9 bool ok;
10 
11 int main()
12 {
13     int a,b,T = 1;
14     while (~scanf("%d%d",&a,&b)) {
15         memset(fa,-1,sizeof(fa));
16         memset(in_degree,0,sizeof(in_degree));
17         memset(c,0,sizeof(c));
18         if (a < 0 && b < 0) break;
19         c[a] = 1;
20         c[b] = 1;
21         in_degree[b]++;
22         while (~scanf("%d%d",&a,&b),a+b) {
23             if (a < 0 && b < 0) return 0;
24             in_degree[b]++;
25             c[a] = 1;
26             c[b] = 1;
27         }
28         int re = 0;
29         int ok = 1;
30         for (int i = 0;i < MAXN; ++ i) if (c[i]){
31             if (in_degree[i] == 0) re ++;
32             if (in_degree[i] > 1) ok = 0;
33         }
34         if (re == 1 && ok) printf("Case %d is a tree.
",T);
35         else printf("Case %d is not a tree.
",T);
36         T++;
37     }
38     return 0;
39 }