并查集，在一些有N个元素的集合应用问题中，我们通常是在开始时让每个元素构成一个单元素的集合，然后按一定顺序将属于同一组的元素所在的集合合并，其间要反复查找一个元素在哪个集合中。并查集是一种树型的数据结构，用于处理一些不相交集合（Disjoint Sets）的合并及查询问题。常常在使用中以森林来表示。
如下几个概念：
1.集合树：所有节点以代表节点为父节点构成的多叉树
2.节点的代表节点：可以理解为节点的父节点，从当前节点出发，可以向上找到的第一个节点
3.集合的代表节点：可以理解为根节点，意味着该集合内所有节点向上走，最终都能到达的节点
合并和查询操作
合并（Union）：把两个不相交的集合合并为一个集合
查询（Find）：查询两个元素是否在同一个集合中
class UnionFindSet:
def UnionFindSet(n):
parents = [0,1...n] # 记录每个元素的parent即根节点 先将它们的父节点设为自己
ranks =[0,0...0] # 记录节点的rank值
# 如下图 递归版本 路径压缩(Path Compression)
# 如果当前的x不是其父节点，就找到当前x的父节点的根节点(find(parents[x])) 并将这个值赋值给x的父节点
def find(x):
if ( x !=parents[x]): # 这里会同步更新该集合中所有的节点的代表节点
parents[x] = find(parents[x])
return parents[x]
# 如下图 根据Rank来合并(Union by Rank)
def union(x,y):
rootX = find(x) # 找到x的根节点rootX
rootY = find(y) # 找到y的根节点rootY
#取rank值小的那个挂到大的那个节点下面，此时两个根节点的rank值并没有发生变化，还是原来的值
if(ranks[rootX]>ranks[rootY]): parents[rootY] = rootX
if(ranks[rootX]<ranks[rootY]): parents[rootX] = rootY
# 当两个rank值相等时，随便选择一个根节点挂到另外一个跟节点上，但是被挂的那个根节点的rank值需要+1
if(ranks[rootX] == ranks[rootY] ):
parents[rootY] = rootX
ranks[rootX]++
来源：
