查看“Union find”的源代码

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

== 算法 ==

=== 添加 ===

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

=== 查询 ===

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

<syntaxhighlight lang=python>
def find_representative(x):
    if x.parent == x:
        return x
    else:
        x.parent = find_representative(x.parent)
        return x.parent
</syntaxhighlight>

=== 合并 ===

{{TODO|union}}

== 相关题目 ==

=== [https://leetcode.com/problems/number-of-provinces/ LeetCode 547. Number of Provinces] ===

Python 解法：
<syntaxhighlight lang=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
</syntaxhighlight>

== 另见 ==

* [[wikipedia:Disjoint-set_data_structure]]