用自己的理解来写好了 有些地方可能不对 不定时更新理解
操作主要为三步 一 初始化
void init() { for (int i = 0; i < n; ++i) { par[i] = i; rank[i] = 0; //用于防退化 } }二 查找
这个为路径压缩 就是每次查找时更新 查找节点（x） 上面所有节点直接使他们连向根节点 每次查找更新
int find(int x) { if (x == par[x]) return x; else return par[x] = find(par[x]); }另一种路径压缩 不过麻烦了些 作为理解
int find(int x){ int t = x; while (x != par[x]){ x = par[x]; } int temp; while (t != x){ temp = par[t]; par[t] = x; t = temp; } return x; }非路径压缩的查找
int find(int x) { while (x != par[x]) x = par[x]; return x; } int find(int x) { if (x == par[x]) return x; return find(par[x]); //之前在前面加了个 x = 完全没有任何意义 }三 合并
void unite(int x,int y){ x = find(x); y = find(y); if (x == y) return; if (rank[x] < rank[y]){ par[x] = y; } else { par[y] = x; if (rank[x] == rank[y]) rank[x]++; } }带防退化的合并 防退化：使较短的树连到较长的树上 合并：让两个 查找节点 的其中一个根节点指向另一个
基本的并查集也就这些了
下面通过分析食物链这个典型题 加深对并查集的理解
带权（关系）并查集
动物王国中有三类动物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），输出假话的总数。 Input 第一行是两个整数N和K，以一个空格分隔。 以下K行每行是三个正整数 D，X，Y，两数之间用一个空格隔开，其中D表示说法的种类。 若D=1，则表示X和Y是同类。 若D=2，则表示X吃Y。 Output 只有一个整数，表示假话的数目。 Sample Input 100 7 1 101 1 2 1 2 2 2 3 2 3 3 1 1 3 2 3 1 1 5 5 Sample Output 3
#include<cstdio> #define maxn 50005 int par[maxn],rank[maxn]; int n,k; void init() { for (int i = 0; i < n; ++i) { par[i] = i; rank[i] = 0; } } int find(int x) { if (x == par[x]) return x; int tx = find(par[x]); rank[x] = (rank[x] + rank[par[x]])%3; return par[x] = tx; } bool unite(int x,int y,int tye) { int tx = find(x); int ty = find(y); if (tx == ty) { if ((rank[x] + tye-1)%3 != rank[y]) return true; else return false; } else { par[ty] = tx; rank[ty] = (rank[x] - rank[y] + tye + 2)%3; return false; } } int main(){ scanf("%d%d",&n,&k); init(); int d,xn,yn; int ans = 0; while (k--) { scanf("%d%d%d",&d,&xn,&yn); if (xn > n || yn > n || xn == yn && d == 2) ans++; else if (unite(xn,yn,d)) ans++; } printf("%d\n",ans); return 0; }算是对不断加入元素关系之间的更新 tye为关系 这题的关系有两种 一种是 0 （同类） 1（相邻作用关系） 根据题中d的条件转化为 0 1 两种 3为三类动物 同类的题可直接套模板
