并查集（含代码）

并查集是一种用来管理元素分组情况的数据结构

作用： 1。查询云元素a和元素b是否属于同一组 2。合并元素a和元素b所在的组。

数组par表示的是父亲的编号，par[x] = x时，x是所在的树的根。

使用rank[MAXN]是使其路径压缩。

int par[MAXN]; //父亲 int rank[MAXN]; //树的高度 //初始化n个元素 void init(int n) { for (int i = 0; i < n; ++i) { par[i] = i; rank[i] = 0; } } //查询树的根 int find(int x) { if (par[x] == x) return x; else return par[x] = find(par[x]); } //合并x和y所属的集合 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]++; } } //判断x和y是否属于同一个集合 bool same(int x, int y) { return find(x) == find(y); }