Powered by GitBook

Union Find

Implementation

class UnionFind(object):
    def __init__(self, size):
        self.parent = []
        self.rank = []
        self.count = size
        for i in range(0, size):
            self.parent.append(i)
            self.rank.append(0)

    def find(self, i):
        if self.parent[i] ！= i: # 不等于就去找最终根节点
            self.parent[i] = self.find(self.parent[i]) 
        return self.parent[i]

    def connected(self, i, j):
        return self.find(i) == self.find(j)

    def union(self, i, j):
        p_i = self.find(i)
        p_j = self.find(j)
        if p_i == p_j:
            return
        if self.rank[p_i] < self.rank[p_j]:
            self.parent[p_i] = p_j
        elif self.rank[p_i] > self.rank[p_j]:
            self.parent[p_j] = p_i
        else:
            self.parent[p_i] =  p_j
            self.rank[p_j] += 1
        self.count -= 1

面试的时候写个简化版

class UnionFind(object):
    def __init__(self, size):
        self.parent = []
        for i in range(size):
            self.parent.append(i)

    def find(self, i):
        if self.parent[i] != i:
            self.parent[i] = self.find(self.parent[i])
        return self.parent[i]

    def connected(self, i, j):
        return self.find(i) == self.find(j)

    def union(self, i, j):
        p_i = self.find(i)
        p_j = self.find(j)
        if p_i == p_j:
            return
        self.parent[p_i] = p_j

复杂度分析

空间复杂度为O(n) 建立一个集合的时间复杂度为O(1), N次合并M查找的时间复杂度。。可以看做是线性的。

References