【算法解惑】并查集

什么是并查集

并查集(Union Find)是一种用于管理分组的数据结构。它具备两个操作：

• 查询元素a和元素b是否为同一组
• 将元素a和b合并为同一组

并查集的结构

可以用树来实现

• 判断两个集合是否属于同一组 = 查看根结点是否相等
• 合并两个数组 = 将两组根节点相连

实现并查集

node = [] //每个节点

//初始化n个节点
//代表每个位置的根结点是他自身
def Init(n):
    for i in range(n):
        node[i] = i

//查找当前元素所在树的根节点(代表元素)
def find(x):
    if x == node[x]:
        return x
    return find(node[x])

//合并元素x， y所处的集合
void Unite(x, y):
    //查找到x，y的根节点
    x = find(x)
    y = find(y)
    if(x == y) 
        return
    //将x的根节点与y的根节点相连
    node[x] = y;
}

//判断x，y是属于同一个集合
bool same(x, y):
    return find(x) == find(y)

优化方向

路径压缩

      0                         0
     / \                      / | \
    1   2       ==>          1  2  3
          \
           3

并查集模版

class UnionFind:
    def __init__(self, n: int):
        self.parent = list(range(n))
        self.size = [1] * n
        self.n = n
        // 当前连通分量数目
        self.setCount = n

    def findset(self, x: int) -> int:
        if self.parent[x] == x:
            return x
        self.parent[x] = self.findset(self.parent[x])  // 直接连接根结点
        return self.parent[x]

    def unite(self, x: int, y: int) -> bool:
        x, y = self.findset(x), self.findset(y)
        if x == y:
            return False
        if self.size[x] < self.size[y]:
            x, y = y, x
        self.parent[y] = x // 让深的树为父节点
        self.size[x] += self.size[y] // 增加深的树的size
        self.setCount -= 1 // 总连通分量减1，也是指组合数
        return True

    def connected(self, x: int, y: int) -> bool:
        x, y = self.findset(x), self.findset(y)
        return x == y // 判断是否连通