Python算法模版——并查集

        并查集常用于与图或树相关的算法题中，一个最为经典应用场景是求无向图的连通分量，为方便大家使用并查集算法，这里为大家提供一个Python的并查集算法模版，并加有详细注释。

class UnionFind:
    def __init__(self, n):
        # n代表总共有n个节点，初始时每个节点以自己为父节点
        # 使用father数组存储各个节点的父节点
        self.father= [x for x in range(n)]
        # 使用size数组，存储每个集合中的数量，初始时每个节点自己为一个集合，故初始值为1
        # 注意只有使用各个集合的根节点的查询出的size值才有意义
        self.size = [1 for _ in range(n)]
        # part表示此时并查集中的集合数量，初始没有任何节点相连，故初始值为n，表示有n个不同的集合
        self.part = n

    def find(self, x):
        # find方法使用递归的方式查询某节点的父节点，并进行路径压缩，
        # 使father数值中直接存储每个节点所连的根节点
        if self.father[x] != x:
            self.father[x] = self.find(self.father[x])
        return self.father[x]

    def union(self, x, y):
        # union方法用于合并两个节点
        # 首先使用find方式找到x，y节点对应的根节点
        root_x = self.find(x)
        root_y = self.find(y)
        # 如果两个根节点相同，表示x，y以及处于一个集合中，返回False表示合并失败
        if root_x == root_y:
            return False
        # 按size合并两个集合，使root_x始终为size值较小的一方
        if self.size[root_x] > self.size[root_y]:
            root_x, root_y = root_y, root_x
        # 合并root_x，root_y，将root_x的父节点置为root_y
        self.father[root_x] = root_y
        # 在root_y所对应的集合中加入root_x所对应的集合中的元素数量
        self.size[root_y] += self.size[root_x]
        # 将集合的总数减一
        self.part -= 1
        return True
    
    def connected(self, x, y):
        # 该方法用于判断x，y两个节点是否属于同一个集合
        return self.find(x) == self.find(y)

    def get_size(self, x):
        # 该方法用于获得x所在集合中的元素数量
        return self.size[self.father[x]]