并查集是一种用来高效处理不相交元素集合的合并（union）和查询（find）问题的数据结构。
并查集的主要作用：将两个不相交集合合并成一个；查找两个元素是否在同一个集合中。
所有与可以实现上述功能的都算并查集，但是一般来说，并查集结构特指利用不相交森林（树结构作为集合）实现的那种并查集。
初始化（增加元素）
并查集并没有真正构造树这种结构，而是通过记录每个节点的父节点，来表示各个元素之间的关系。这个记录用list来实现。
拿到一个集合，首先进行并查集初始化，此时需要将每个元素看做独立的一个集合（一棵树），于是各自的parent指向自己。
parent = list()
for i in items:
parent[i] = i如果有n个item，那么就有了n棵树。
查询
查询一个元素的代表元素，其实就是其根节点，最简单的办法：只需要沿着parent一路向上找过去即可。
def find(x):
if parent[x] == x:
return x
else:
return find(parent[x])原理和实现都很简单。但是有一个问题：如果这棵树是skewed，那么，就退化成了链表。因此，我们希望树尽量的浅。也就是说，尽可能将所有属于这个集合的item都直接挂在根节点上，这样都能一步找到。这个思路就是：路径压缩，改进也只用一行代码即可：
def find(x):
if parent[x] == x:
return x
else:
# return 之前先把x挂在root上，然后返回下一级节点
parent[x] = find(parent[x])
return parent[x]合并
合并两个元素所在的集合：首先判断是否在一个集合？是的话不需要合并，否则的话将一个的根节点挂在另一个的根节点底下。
def union(x, y):
if find(x) == find(y):
return
else:
parent[find(x)] = find(y)
return这个操作也是可以优化的，因为如果一直都是将左变量的root挂在右变量的root下，有可能随着合并树变偏斜，退化成链表。为了保持平衡，一般需要再维护一个变量，比如size或者rank，使得每次都是小树挂在大树底下。
size就是元素数量，因此union之后新树（集合）需要把size更新成两合并者之和。
rank是树的秩，定义：两个rank不同时，为两个子树的rank的最大值；相同时，为rank+1。
复杂度
可以证明，并查集的操作复杂度近似于常数复杂度。（实际上是O(a(n))，其中a(n)为反阿克曼函数，增长极缓慢。）