题意：中文题，不翻译了。http://poj.org/problem?id=1182
解法：并查集的基础题，好题。在之前我还做过POJ 1861，2524，1611三道水题，算是为了并查集入门。不过，现在做完1182才觉得，只要认真地把1182搞懂了，并查集这个知识点就真的完全搞懂了。
不过，这道题我觉得还是有一定难度的，可以考虑先做它的简化版，POJ 1703。题解见POJ 1703 Find them, Catch them(附题目翻译)。
本人智商有限，一直没有搞出来，看得别人的题解。(只看代码部分就能看懂，有大量注释)http://blog.csdn.net/spark_007/article/details/9445949。
另外，我还写了一份代码，由于是在没有完全弄懂并查集的时候写得，写得比较搓。struct node里面，f表示父亲节点，r表示与父亲节点的关系，x表示与该树根节点的关系(0表示同类，1表示吃别人，2表示被吃)。
注意：一般，这种题子节点和父亲节点的关系如果有三种，比如这道题为子节点和父节点同类，子节点吃父节点，子节点被父节点吃，则最好将子节点父节点同类设为r=0，其余一个为r=1另一个为r=2。这样设的好处是，子节点与父亲节点的关系为r，同时父亲节点与子节点的关系为3-r，推导关系转化公式的时候比较好推导。
Ps：此题为单组数据读入，如果用while (scanf () != EOF)会错，不明绝厉，代码查错查了近一个晚上- -。
tag:并查集, good
1 /* 2 * Author: Plumrain 3 * Created Time: 2013-11-25 20:00 4 * File Name: G-POJ-1182-2.cpp 5 */ 6 #include <iostream> 7 #include <cstdio> 8 9 using namespace std; 10 11 const int maxn = 50005; 12 13 struct node{ 14 int f, r, x; 15 }; 16 17 int n, k; 18 node a[maxn]; 19 20 int find(int x) 21 { 22 if (x == a[x].f){ 23 a[x].r = a[x].x = 0; 24 return x; 25 } 26 27 int y = a[x].f; 28 if (y == a[y].f){ 29 a[x].x = a[x].r; 30 return y; 31 } 32 33 int ret = find(y); 34 a[x].x = (a[x].r + a[y].x) % 3; 35 return ret; 36 } 37 38 void merge(int x, int y, int d, int t1, int t2) 39 { 40 t1 = find(x); 41 t2 = find(y); 42 a[t1].f = t2; 43 a[t1].r = a[t1].x = ((3-a[x].x) + a[y].x + d-1) % 3; 44 } 45 46 bool gao(int d, int x, int y) 47 { 48 if ((d == 2 && x == y) || x >= n || y >= n) 49 return false; 50 51 int t1 = find(x), t2 = find(y); 52 if (t1 == t2){ 53 if (d == 1) 54 if (a[x].x != a[y].x) return false; 55 if (d == 2) 56 if ((a[x].x%3) != ((a[y].x+1)%3)) return false; 57 } 58 else 59 merge(x, y, d, t1, t2); 60 return true; 61 } 62 63 void init() 64 { 65 for (int i = 0; i < n; ++ i){ 66 a[i].f = i; 67 a[i].r = a[i].x = 0; 68 } 69 } 70 71 int main() 72 { 73 scanf ("%d%d", &n, &k); 74 init(); 75 76 int d, x, y, ans = 0; 77 for (int i = 0; i < k; ++ i){ 78 scanf ("%d%d%d", &d, &x, &y); 79 if (!gao(d, x-1, y-1)) ++ ans; 80 } 81 printf ("%d ", ans); 82 return 0; 83 }