題目鏈接：http://poj.org/problem?id=1308
大意就是給一些點(diǎn)的指向關(guān)系，最后問能否組成一棵樹。
用并查集寫了，每次給的兩個(gè)點(diǎn)不在相同集合，就合并，合并一次相當(dāng)于多增加了一條邊，所以在合并的時(shí)候記錄一下邊數(shù)，如果合并過程中出現(xiàn)了環(huán)，那么說明不是一棵樹，如果之后點(diǎn)數(shù)與邊數(shù)加一不相等，也不是一棵樹，所以需要記錄點(diǎn)的個(gè)數(shù)，我用的是string類，每次find一下，最后求string的長度，有點(diǎn)兒偷懶屌絲了，不過發(fā)覺確實(shí)是方便，但是我的代碼因此奇葩了不少……
一定要注意，空樹也是一棵樹，需要加條件判斷，我就是因?yàn)樯倭艘粋€(gè)條件，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