并查集快速查找学习笔记

什么是并查集？

并查集（Disjoint Set）是一种树型的数据结构，用于处理一些不相交集合（Disjoint Sets）的合并及查询问题。常常在使用中以森林来表示。

并查集支持以下两个操作：

• 查找元素 x 所在的集合
• 合并元素 x 和 y 所在的集合

实现并查集

我们可以使用一个数组 parent[] 来表示每个节点的父节点，初始时每个节点的父节点为它自己。当进行合并操作时，只需要将其中一个节点的父节点设置为另一个节点即可。查找操作则是不断地沿着父节点往上跳，直到找到根节点。具体实现如下：

pythonCopy Code
class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
    
    def find(self, x):
        if self.parent[x] == x:
            return x
        self.parent[x] = self.find(self.parent[x])
        return self.parent[x]
    
    def union(self, x, y):
        px, py = self.find(x), self.find(y)
        self.parent[py] = px

实例

假设有 n 个人，编号从 0 到 n-1，他们之间可能存在朋友关系，即某些人互为朋友。我们可以使用并查集来维护朋友圈的数量，具体实现如下：

pythonCopy Code
def findCircleNum(M: List[List[int]]) -> int:
    n = len(M)
    uf = UnionFind(n)
    for i in range(n):
        for j in range(i+1, n):
            if M[i][j] == 1:
                uf.union(i, j)
    count = 0
    for i in range(n):
        if uf.parent[i] == i:
            count += 1
    return count

其中，M 表示一个 n*n 的矩阵，M[i][j] = 1 表示第 i 个人和第 j 个人是朋友关系。我们遍历矩阵，将所有朋友之间的节点进行合并，最后统计有多少个根节点（即朋友圈的个数），即可得到答案。

以上就是并查集的学习笔记，如果有什么问题欢迎随时提出！