2020-3-1 并查集小总结

0X00 模板

class UnionFind:
    def __init__(self, n):
        self.fathers = [i for i in range(n)]
        # 记录有几个联通分量
        self.count = n
        # 记录每个联通分量有几个元素 
        self.nums = [1 for _ in range(n)]
    
    def find(self,  x):
        if self.fathers[x] != x:
            self.fathers[x] = self.find(self.fathers[x])
        return self.fathers[x]
    
    def union(self, x, y):
        fx, fy = self.find(x), self.find(y)
        if fx == fy: return False
        self.count -= 1
        self.nums[fy] +=  self.nums[fx]
        self.fathers[fx] = fy
        return True

0X01 有哪些问题适合并查集

• 查询两个元素是否在同一个集合内

leetcode 323. Number of Connected Components in an Undirected Graph

• 合并两个元素所在的集合

• 查询某个元素所在集合的元素个数

leetcode 261. Graph Valid Tree

• 查询当前集合的个数

0X02 高阶并查集

二维并查集

leetcode 305. Number of Islands II

模板在此:

class UnionFind:
    def __init__(self, m, n):
        l = m * n
        self.m = m
        self.n = n
        self.fathers = [i for i in range(l)]
    
    def pos2idx(self, p):
        x, y = p
        return x * self.n + y
    
    def idx2pos(self, idx):
        return (idx // m, idx % n)
    
    def find(self, idx):
        if self.fathers[idx] != idx:
            self.fathers[idx] = self.find(self.fathers[idx])
        return self.fathers[idx]
    
    def union(self, p1, p2):
        idx1, idx2 = self.pos2idx(p1), self.pos2idx(p2)
        f1, f2 = self.find(idx1), self.find(idx2)
        if f1 == f2:
            return False
        self.fathers[f1] = self.fathers[f2]
        return True