题目链接：http://poj.org/problem?id=1308
大意就是给一些点的指向关系，最后问能否组成一棵树。
用并查集写了，每次给的两个点不在相同集合，就合并，合并一次相当于多增加了一条边，所以在合并的时候记录一下边数，如果合并过程中出现了环，那么说明不是一棵树，如果之后点数与边数加一不相等，也不是一棵树，所以需要记录点的个数，我用的是string类，每次find一下，最后求string的长度，有点儿偷懒屌丝了，不过发觉确实是方便，但是我的代码因此奇葩了不少……
一定要注意，空树也是一棵树，需要加条件判断，我就是因为少了一个条件，WA了好几次……
附代码：
view code
1 #include <iostream>
2 #include <cstdio>
3 #include <cstdlib>
4 #include <cstring>
5 #include <cmath>
6 #include <algorithm>
7 using namespace std;
8 #define N 100000
9 int p[N], n, r;
10 string num;
11 int find(int x)
12 {
13 return p[x] != x ? p[x] = find(p[x]) : x;
14 }
15 void init()
16 {
17 for (int i = 1; i < N; i++)
18 p[i] = i;
19 n = 0; r = 0;
20 }
21 int main()
22 {
23 int t = 1;
24 int x, y;
25 int r1, r2;
26 bool j = 1;
27 init();
28 while (scanf("%d%d", &x, &y) != EOF)
29 {
30 if (x < 0 || y < 0) break;
31 if (x == 0 && y == 0)
32 {
33 int l = num.size();
34 if (l != r + 1 && l > 0) j = 0;
35 if (j) printf("Case %d is a tree.\n", t++);
36 else printf("Case %d is not a tree.\n", t++);
37 init();
38 num.clear();
39 j = 1;
40 continue;
41 }
42 if (x == y) j = 0;
43 if (num.find(x - '0') == -1) num.push_back(x - '0');
44 if (num.find(y - '0') == -1) num.push_back(y - '0');
45 r1 = find(x); r2 = find(y);
46 if (r1 == r2) j = 0;
47 if (r1 != r2)
48 {
49 p[r2] = r1;
50 r++;
51 }
52 }
53 return 0;
54 }
55