【HDOJ】1325 Is It A Tree?

并查集。需要考虑入度。
 1 #include <stdio.h>
 2 #include <string.h>
 3 
 4 #define MAXNUM 10005
 5 
 6 int bin[MAXNUM];
 7 int degree[MAXNUM];
 8 int nums[MAXNUM];
 9 
10 int find(int x) {
11     int r = x;
12 
13     while (bin[r] != r)
14         r = bin[r];
15 
16     return r;
17 }
18 
19 int main() {
20     int x, y, fx, fy, n, case_n = 0;
21     int i, flg;
22 
23     while (1) {
24         scanf("%d %d", &x, &y);
25         if (x<0 && y<0)
26             break;
27         memset(degree, 0, sizeof(degree));
28         n = 0;
29         ++case_n;
30         if (x==0 && y==0) {
31             printf("Case %d is a tree.
", case_n);
32             continue;
33         }
34         for (i=0; i<MAXNUM; ++i)
35             bin[i] = i;
36         fx = find(x);
37         fy = find(y);
38         bin[fy] = fx;
39         degree[y]++;
40         flg = 1;
41         nums[n++] = x;
42         nums[n++] = y;
43         while (1) {
44             scanf("%d %d", &x, &y);
45             if (x==0 && y==0)
46                 break;
47             fx = find(x);
48             fy = find(y);
49             if (fx != fy) {
50                 bin[fy] = fx;
51                 degree[y]++;
52             } else {
53                 bin[fy] = fx;
54                 degree[y]++;
55                 flg = 0;
56             }
57             nums[n++] = x;
58             nums[n++] = y;
59         }
60         fx = find(nums[0]);
61         for (i=1; i<n; ++i) {
62             fy = find(nums[i]);
63             if (fx != fy) {
64                 flg = 0;
65                 break;
66             }
67         }
68         for (i=0; i<n; ++i) {
69             if (degree[nums[i]] > 1) {
70                 flg = 0;
71                 break;
72             }
73         }
74         if (flg)
75             printf("Case %d is a tree.
", case_n);
76         else
77             printf("Case %d is not a tree.
", case_n);
78     }
79 
80     return 0;
81 }