Union-Find 併查集

更新紀錄：

2022.03.01 更新網路資料 2 的連結

網路資料：

1. Link 中文維基百科
2. Link Robert Sedgewick 教授的 Algorithm 4th 配套投影片

觀念紀錄：

Union-Find 是一種 data structure 也可以是一種類型的問題。

問題的主要描述是：

• Find(x, y): 回傳 x, y 是否屬於同一個 set
• Union(x, y): 合併 x, y 所屬的 set

之所以會說是一種 data structure 是因為，實務上高效率解決這類問題的作法是一種特定的資料結構。

Python 程式碼:

class UnionFind:
    def __init__(self, n):
        self.id = [i for i in range(n)]
        self.sz = [1 for _ in range(n)]
        
    def root(self, i):
        while i != self.id[i]:
            self.id[i] = self.id[self.id[i]]
            i = self.id[i];
        return i
    
    def find(self, p, q):
        return self.root(p) == self.root(q)
    
    def unite(self, p, q):
        i = self.root(p)
        j = self.root(q)
        if self.sz[i] <= self.sz[j]:
            self.id[i] = j
            self.sz[j] += self.sz[i]
        else:
            self.id[j] = i
            self.sz[i] += self.sz[j]