一、概念及其介绍
并查集是一种树型的数据结构，用于处理一些不相交集合的合并及查询问题。
并查集的思想是用一个数组表示了整片森林（parent），树的根节点唯一标识了一个集合，我们只要找到了某个元素的的树根，就能确定它在哪个集合里。
二、适用说明
并查集用在一些有 N 个元素的集合应用问题中，我们通常是在开始时让每个元素构成一个单元素的集合，然后按一定顺序将属于同一组的元素所在的集合合并，其间要反复查找一个元素在哪个集合中。这个过程看似并不复杂，但数据量极大，若用其他的数据结构来描述的话，往往在空间上过大，计算机无法承受，也无法在短时间内计算出结果，所以只能用并查集来处理。
三、并查集的基本数据表示
如上图 0-4 下面都是 0，5-9 下面都是 1，表示 0、1、2、3、4 这五个元素是相连接的，5、6、7、8、9 这五个元素是相连的。
再如上图 0、2、4、6、8 下面都是 0 这个集合，表示 0、2、4、6、8 这五个元素是相连接的，1、3、5、7、9 下面都是 1 这个集合，表示 0，1、3、5、7、9 这五个元素是相连的。
构造一个类 UnionFind，初始化, 每一个id[i]指向自己, 没有合并的元素：
public UnionFind1(int n) {
count = n;
id = new int[n];
// 初始化, 每一个id[i]指向自己, 没有合并的元素
for (int i = 0; i < n; i++)
id[i] = i;
}
查找¶
通俗地讲一个故事：几个家族进行宴会，但是家族普遍长寿，所以人数众多。由于长时间的分离以及年龄的增长，这些人逐渐忘掉了自己的亲人，只记得自己的爸爸是谁了，而最长者（称为「祖先」）的父亲已经去世，他只知道自己是祖先。为了确定自己是哪个家族，他们想出了一个办法，只要问自己的爸爸是不是祖先，一层一层的向上问，直到问到祖先。如果要判断两人是否在同一家族，只要看两人的祖先是不是同一人就可以了。
在这样的思想下，并查集的查找算法诞生了。
# Python Version
fa = [0] * MAXN # 记录某个人的爸爸是谁，特别规定，祖先的爸爸是他自己
# 递归
def find(x):
# 寻找x的祖先
if fa[x] == x:
return x # 如果x是祖先则返回
else:
return find(fa[x]) # 如果不是则 x 的爸爸问 x 的爷爷
# 非递归
def find(x):
while x != fa[x]: # 如果 x 不是祖先，就一直往上一辈找
x = fa[x]
return x # 如果 x 是祖先则返回这样的确可以达成目的，但是显然效率实在太低。为什么呢？因为我们使用了太多没用的信息，我的祖先是谁与我父亲是谁没什么关系，这样一层一层找太浪费时间，不如我直接当祖先的儿子，问一次就可以出结果了。甚至祖先是谁都无所谓，只要这个人可以代表我们家族就能得到想要的效果。把在路径上的每个节点都直接连接到根上，这就是路径压缩。
# Python Version
def find(x):
if x != fa[x]: # x 不是自身的父亲，即 x 不是该集合的代表
fa[x] = find(fa[x]) # 查找 x 的祖先直到找到代表，于是顺手路径压缩
return fa[x]
合并¶
宴会上，一个家族的祖先突然对另一个家族说：我们两个家族交情这么好，不如合成一家好了。另一个家族也欣然接受了。
我们之前说过，并不在意祖先究竟是谁，所以只要其中一个祖先变成另一个祖先的儿子就可以了。
# Python Version
def unionSet(x, y):
# x 与 y 所在家族合并
x = find(x)
y = find(y)
fa[x] = y # 把 x 的祖先变成 y 的祖先的儿子