1. 前言
并查集（Union Find Set），也称为不相交集数据结构（Disjointed Set Data Structure），两个名字各自概括了这一数据结构的部分特征。简单地讲，并查集维护了一列互不相交的集合S1、S2、S3、…，支持查找（find）与合并（union）两种操作。
- find
找到元素所在的集合，通常返回该集合的代表元（representative）
元素a与元素b是否属于同一个集合，只要判断find（a）与find（b）是否相等 - union
将两个集合合并为一个集合
将元素a与元素b所在的集合合并为一个集合，使用union（a，b）
我的实现在这里
2. 原理
2.1 基础算法
UnionFindSet用树表示集合，所谓维护一列互不相交的集合也就是有许多棵树。每棵树的元素属于一个集合，树根的元素就是集合的代表元，所以UnionFindSet实际上维护了一个多棵树构成的森林。
- find(x)就是找x所在的树的树根
- union(x, y)就是合并x和y所在的树
来看UnionFindSet的定义：
class UnionFindSet {
public:
UnionFindSet(int n);
int Find(int x);
void Union(int x, int y);
private:
std::vector<int> parent;
};
与常见的树形数据结构不同，并查集的链接关系不是从parent指向child而是从child指向parent，这个链接信息保存在parent数组里。
- 若parent[x] == x，则x就是x所在树的树根
- 若parent[x] != x，则x是parent[x]的子节点
解释完parent的含义，Find的实现方法也就呼之欲出了。
int UnionFindSet::Find(int x) {
if (parent[x] == x)
return x;
else
return Find(parent[x]);
}
构造函数UnionFindSet(int n)表示最初有n个互不相交的集合，代表元分别为0、1、2、…(n-1)。
UnionFindSet::UnionFindSet(int n) {
parent.resize(n);
for (int i = 0; i < n; ++i) {
parent[i] = i;
}
}
要合并两棵树，只要把一棵根节点的parent设为另一棵树的根节点。
void UnionFindSet::Union(int x, int y) {
int root_x = Find(x);
int root_y = Find(y);
if (root_x == root_y)
return;
parent[root_y] = root_x;
}
用图形解释find和union中parent的作用，其中child在下层，parent在上层。
3的parent是2，那么调用find(3)时：
- parent[3] = 2，调用find(2)
- parent[2] = 2，返回2
调用union(1, 3)时：
- 调用find(1)，得到root_x = 0
- 调用find(3)，得到root_y = 2
- parent[2] = 0
2.2 优化合并
并查集就是一组树构成的森林，与通常的搜索树相比只是链接关系从parent->child变成了child->parent，所以也会出现搜索树中的问题。极端情况下n个节点像链表那样构成n层，对于最底层的节点，find复杂度自然是O(n)，而union由于调用find复杂度也会变成O(n)。
既然树的高度影响效率，那么可以设法避免高树出现，也就是本小节的优化合并；也可以设法把高树变矮，也就是下一小节的路径压缩。
优化合并就是优化union操作，简单粗暴地讲，就是合并时永远把矮树作为高树的子树。判断哪棵树比较矮有union-by-size和union-by-height两种做法，union-by-height是在类中添加height数组记录每个节点的高度，union-by-size是在类中添加size数组记录每个节点的子节点数量，两者效果完全相同。我采用union-by-height，感兴趣union-by-size的可以看这里
在类中添加height数组：
class UnionFindSet {
public:
UnionFindSet(int n);
int Find(int x);
void Union(int x, int y);
void Display(void);
private:
std::vector<int> parent;
std::vector<int> height;
};
修改构造函数UnionFindSet(int n)：
UnionFindSet::UnionFindSet(int n) {
parent.resize(n);
height.resize(n);
for (int i = 0; i < n; ++i) {
parent[i] = i;
height[i] = 0;
}
}
新的union算法：
void UnionFindSet::Union(int x, int y) {
int root_x = Find(x);
int root_y = Find(y);
if (root_x == root_y)
return;
if (height[root_x] > height[root_y]) {
parent[root_y] = root_x;
} else if (height[root_x] < height[root_y]) {
parent[root_x] = root_y;
} else {
parent[root_y] = root_x;
++height[root_x];
}
}
注意只有根节点高度相同时需要更新height，因为两棵树高度不相等时矮的那棵至少比高的矮一层。因此对于有n个节点的并查集，height的最大值为lgn，所以find和union的算法复杂度都至多为O(lgn)。
2.3 路径压缩
路径压缩就是改造find操作，直接来看代码：
int UnionFindSet::Find(int x) {
if (parent[x] == x)
return x;
else {
int result = Find(parent[x]);
parent[x] = result;
return result;
}
}
也就是说在查找时，把查找路径上节点的parent都设为根节点，从而把这棵树「压平」，加速以后的查找。用图形演示find(4)就是：
这时find操作也会改变树高，所以height数组里的值就不是准确的树高，而是估计树高（estimated height），或者称为秩（rank），这时做法也成为union-by-rank。
3. 应用
并查集可以用于检测无向图中是否存在环。假设无向图中有v个节点和e条边，用伪代码形式写就是：
bool detect_cycle(v, e) {
u = UnionFindSet(v)
for (int i = 0; i < e.size; ++i) {
(p, q) = e(i); // 取得第i条边的两个节点
if (u.find(p) == u.find(q))
return true;
u.union(p, q);
}
return false;
}
所以可以把并查集用在kruskal最小生成树算法里，实现可以参考这里
注意与BFS/DFS相比，并查集检测速度快，但只能检测环的存在，不能确定哪些节点构成了环。
4. 参考资料
- Disjoint-set data structure（Wiki）：
https://en.wikipedia.org/wiki/Disjoint-set_data_structure - Disjoint-set data structure（Mathblog）：
http://www.mathblog.dk/disjoint-set-data-structure/
5. 附录：关于代表元
下图是一张典型的无向图，有a、b、c、d、e五个节点：
记** S(x) **表示包含节点x的极大连通子图里节点的集合，显然有：
S(a) = S(b)= S(c) = { a，b，c }
S(d) = S(e) = { d，e }
不同的集合有 {a，b，c} 和 {d，e} 两个，而且它们互不相交。代表元是一个集合里的典型元素，可以从集合里任意选取，比如 {a，b，c} 的代表元可以用a，也可以用b或c。由于集合互不相交，所以代表元互不相同，判断「两个元素是否属于同一个集合」等价于判断「两个元素所在集合的代表元是否相等」。
**find(x) **就是找到元素x所在集合的代表元。
分别取a、d为两个集合的代表元，那么有：
find(a) = find(b) = find(c) = a
find(d) = find(e) = d
b和e不在同一个集合里，相应的有find（b）不等于find（e）。
现在我们在原图里添加一条连接b和d的边：
发生了什么事情？图上两个互相不连通的部分结合了，这时应该有：
S(a) = S(b)= S(c) = S(d) = S(e) = { a，b，c，d，e }
**union(x, y) **就是将元素x和元素y所在的集合合并成一个集合。
union(b, d)之后，b所在的、以a为代表元的集合，与d所在的、以d为代表元的集合合成了一个大的新集合，将这个新集合代表元取为a，则有：
find(a) = find(b) = find(c) = find(d) = find(e) = a
b和e现在在同一个集合里，所以有find（b）等于find（e）。
