Union find

并查集：用于处理一些不交集（Disjoint sets）的合并及查询问题。

算法

添加

新添加一个元素时，它的 parent 是它自己。

查询

每个集合的代表是集合的根节点。在查询时进行路径压缩。

def find_representative(x):
    if x.parent == x:
        return x
    else:
        x.parent = find_representative(x.parent)
        return x.parent

合并

TODO

union

相关题目

LeetCode 547. Number of Provinces

Python 解法：

def findCircleNum(self, isConnected: List[List[int]]) -> int:
    '''
    Union Find solution. Begins by seting the number of provinces to the
    number of cities, then union each pair of the connected cities. If they
    belong to different sets before the union, reduce the number of
    provinces by 1 (unioned two cities into one province).
    '''
    city_num = len(isConnected)
    representative = [i for i in range(city_num)]
                                                                            
    def find_repr(c):
        if representative[c] == c:
            return c
        else:
            representative[c] = find_repr(representative[c])
            return representative[c]
                                                                            
    ret = city_num
    for i in range(city_num):
        for j in range(i + 1, city_num):
            if not isConnected[i][j]:
                continue
            if (ri := find_repr(i)) != (rj := find_repr(j)):
                # Connected cities are in different sets. Union them and
                # reduce the number of provinces
                representative[ri] = rj
                ret -= 1
    return ret

另见

• wikipedia:Disjoint-set_data_structure