Union_Find_Set 并查集

并查集（Union_Find_Set）是求解连通分量或者等价类快速高效的方法，算法采用了树形的数据结构。

问题描述：已知多对节点的关系，比如（1，2），（2， 3），（4，5），求解其等价类。

问题解析：如果两个节点在同一棵树中，那么可以将其视为等价，如何判断节点在同一棵树中呢？树的根(root)作为树的representative element，可以帮助我们测试节点是否在同一棵树中。

初始化的时候，每个节点都将其本身设置为root，即root[i] = i;随着(u, v)的引入，如何合并树呢？即union(u, v)如何去实现。假如u, v不在同一棵树中，我们可以简单地将 v 所在树的根节点root变成 u 所在树的根节点root的孩子child，这样就完成了 u, v 所在两棵树的合并，以此类推。

通过以上解析，有个问题就是如何获取树的根？这里设置一个全局数组 root[N](root[i]存放第i个节点的长辈，只有当 root[i] == i 的时候才断定 i 就是树根)；然后设计一个函数 find(i)，该函数返回节点i所在树的根，即find()返回representative element。

综上分析设计并查集的两个操作函数(Python风格)，union(u, v) 和 find(i)：

'''
Find
'''
def find(i):
    if root[i] == i:
        return root[i]
    else:
        root[i] = find(root[i]) # 路径压缩(path compression)，从i节点到根节点路径上的所有节点的root值均被设置成根节点
        return root[i]

'''
Union
'''
def union(u, v):
    if find(u) == find(v): # 同一棵树中
        pass
    else: # 将u树的根节点同时作为v树的根节点，完成了树的合并
        root[find(v)] = find(u)

以上两个函数

union(u, v)：合并 u 和 v 所在的集合（呈树形结构）。

find(u)：返回 u 所在树形结构集合的根。

给个链接供大家参考：