并查集的英文名理论上是 disjoint-set data structure (also called union–find data structure or merge–find set) 。所以说“并查集”这个词的来源，是其第二个和第三个英文名。
确定两个元素属于同一个集合需要Find找出他们的集合的代表元素再比较。
路径压缩
英文名是 Path compression 。
由于是迭代版本的实现，所以只使用路径压缩也不会导致 stack overflow 。
struct DisjointSet {
static const int MAXN = 200000;
int n, rt[MAXN + 5];
void Init(int _n) {
n = _n;
for(int i = 1; i <= n; i++)
rt[i] = i;
}
int Find(int u) {
int r = rt[u];
while(rt[r] != r)
r = rt[r];
int t;
while(rt[u] != r) {
t = rt[u];
rt[u] = r;
u = t;
}
return r;
}
bool Union(int u, int v) {
u = Find(u), v = Find(v);
if(u == v)
return false;
else {
rt[v] = u;
return true;
}
}
};
路径压缩 + 按size合并
英文名是 union by size
struct DisjointSet {
static const int MAXN = 200000;
int n, rt[MAXN + 5], siz[MAXN + 5];
void Init(int _n) {
n = _n;
for(int i = 1; i <= n; i++) {
rt[i] = i;
siz[i] = 1;
}
}
int Find(int u) {
int r = rt[u];
while(rt[r] != r)
r = rt[r];
int t;
while(rt[u] != r) {
t = rt[u];
rt[u] = r;
u = t;
}
return r;
}
bool Union(int u, int v) {
u = Find(u), v = Find(v);
if(u == v)
return false;
else {
if(siz[u] < siz[v])
swap(u, v);
rt[v] = u;
siz[u] += siz[v];
return true;
}
}
};
扩展域并查集
通常有一些题目，某个元素x不在集合1中就在集合2中，这个时候就把x拆成两个点 (x_1) （表示x在集合1中）和 (x_2) （表示x在集合1中）。在需要的时候还可以在并查集中加入两个特殊的点 (TRUE) 和 (FALSE) ，根据题目的限制以及所给的一些额外信息，上面的一些信息会变成等价（可以互相推出）的，这个时候由于并查集本身是维护等价类的，就可以把对应的信息连边，也就是合并等价类。
一些思考：
1、 Union 操作无论结果是 true 还是 false ，其结果都是本身是等价类的信息现在也依然是等价类。
2、恒为真的信息可以和 (TRUE) 连边，恒为假的信息可以和 (FALSE) 连边。
3、不矛盾的条件是，对于每个点x（指普通的点，有些特殊的点确实分到了集合3中）(x_1) 和 (x_2) 不在同一集合中，且 (TRUE) 和 (FALSE) 也不在同一集合中。