Union Find Set（并查集）

并查集是一个广泛用于DFS，BFS等图相关问题时的数据结构，最基本的功能就是find和union，还有一些特殊的扩展功能如找寻某个特定联通分量的结点个数或者整个图中的联通分量的个数等等

• 并查集一般是用一个数组来表示的，这是因为一般OJ的图问题都会使用一个独特的值（一般是数字）来表示一个图结点，所以可以使用数组的下标来表示一个图结点，对应的值来表示此结点所在的联通分量的头结点，当然如果数组不允许的情况下Python中的dict数据结构也可以用来表示并查集，此时并查集和Trie树的实现就很相似了，下面是数组形式的并查集实现

parent = [-1] * n        # -1表示此结点以自己本身为头结点

• find的功能是搜寻指定结点所在分量的头结点，没有进行路径压缩优化时最坏时间复杂度是O(n)，进行优化后摊还为O(1)，下面是优化后代码

def find(parent, node):
    if parent[node] == -1:
        return node
    parent[node] = find(parent, parent[node])                      # 此行进行了路径压缩
    return parent[node]

• union的功能是将两个制定的结点的联通分量连接在一起，摊还后也是O(1)的时间复杂度，下面是代码

def union(parent, a, b):
    cur_a = find(parent, a)
    cur_b = find(parent, b)
    if cur_a != cur_b:                # 这里判断两个结点是不是在同一个联通分量里面，如果是不用进行合并
        parent[a] = b                 # 这里的连接操作也可以是parent[b] = a，取决于具体题目要求