综合例题： poj 1182 食物链 http://poj.org/problem?id=1182 动物王国中有三类动物A、B、C，这三类动物的食物链是：A吃B，B吃C，C吃A。 现有N个动物，以1~N编号。每个动物都是A、B、C中的一种，但是我们并不知道它到底是哪一种。 有人用两种说法对这N个动物所构成的食物链关系进行描述： 第一种说法是"1 X Y"，表示X和Y是同类。 第二种说法是"2 X Y"，表示X吃Y。 此人对N个动物，用上述两种说法，一句接一句地说出K句话，这K句话有的是真的，有的是假的。当一句话满足下列三条之一时，这句话就是假话，否则就是真话。 1） 当前的话与前面的某些真的话冲突，就是假话； 2） 当前的话中X或Y比N大，就是假话； 3） 当前的话表示X吃X，就是假话。 你的任务是根据给定的N（1 <= N <= 50,000）和K句话（0 <= K <= 100,000），输出假话的总数。 代码：
#include <iostream> #include <stdio.h> using namespace std; const int maxn = 50005; int s[maxn]; //集合 int d[maxn]; // 0：同类； 1：吃； 2：被吃 int ans; void init_set(){ //初始化 for(int i = 0; i <= maxn; i++) { s[i] = i; d[i] = 0; } } int find_set(int x){ //带权值的路径压缩 if(x != s[x]) { int t = s[x]; //记录父结点 s[x] = find_set(s[x]); //路径压缩。递归最后返回的是根结点 d[x] = (d[x] + d[t]) % 3; //权值更新为x到根节点的权值 } return s[x]; } void merge_set(int x, int y, int relation){ //合并 int rootx = find_set(x); int rooty = find_set(y); if (rootx == rooty){ if ((relation - 1) != ((d[x] - d[y] + 3) % 3)) //判断矛盾 ans++; } else { s[rootx] = rooty; //合并 d[rootx] = (d[y] - d[x] + relation - 1) % 3; //更新权值 } } int main(){ int n, k; cin >> n >> k; init_set(); ans = 0; while (k--){ int relation, x, y; scanf("%d%d%d",&relation,&x,&y); if ( x > n || y > n || (relation == 2 && x == y ) ) ans++; else merge_set(x,y,relation); } cout << ans; return 0; }代码解析：并查集板子无非就是三点：1.初始化。2.查找父节点。3.合并。 而这道题采取了优化，也就是路径压缩。
void init_set(){ //初始化 for(int i = 0; i <= maxn; i++) { s[i] = i; d[i] = 0; } }初始化不必多说，每个点的初始父节点是自己。而这道题是带权值的，所以还得初始化权值为；
int find_set(int x){ //带权值的路径压缩 if(x != s[x]) { int t = s[x]; //记录父结点 s[x] = find_set(s[x]); //路径压缩。递归最后返回的是根结点 d[x] = (d[x] + d[t]) % 3; //权值更新为x到根节点的权值 } return s[x]; }查找父节点的函数：这个点也是优化的一个点，在查的时候就更新节点的父节点，直到节点的父节点是根节点，这样下次再查找时就可以直接找到其根节点，权值也更新为到根节点的权值，至于余3则是题目所需。
void merge_set(int x, int y, int relation){ //合并 int rootx = find_set(x); int rooty = find_set(y); if (rootx == rooty){ if ((relation - 1) != ((d[x] - d[y] + 3) % 3)) //判断矛盾 ans++; } else { s[rootx] = rooty; //合并 d[rootx] = (d[y] - d[x] + relation - 1) % 3; //更新权值 } }合并代码也是最核心的代码，首先找到2节点的根节点，若根节点相同，则说明二者已有关系，接下来判断他们的关系是否矛盾，判断矛盾语句则是在纸上推导出来的。若根节点不同，则合并，跟新权值，更新权值的代码也要根据题意推导。
合并过程也可以优化 合并元素x和y时，先搜到它们的根结点，然后再合并这两个根结点，即把一个根结点的集改成另一个根结点。这两个根结点的高度不同，如果把高度较小的集合并到较大的集上，能减少树的高度。
