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]

python defaultdict 的用法

主要目標：

紀錄 defaultdict 的概念跟常見用法。

說明：

帶有預設值的 dictionary ，第一個參數是一個可呼叫的物件，後面接的參數會直接給 dict 當參數使用。

例如：

defaultdict(int, {'a': 10, 'b': 20})

等同於會呼叫的意思：

dict({'a': 10, 'b': 20})

整理最常用的方法： 

1. 要計算所有的東西有多少個： 

d = defaultdict(int) 

d[x] += 1 

2. 要把同一個 key 的東西串在一起： 

d = defaultdict(list) 

d[x].append(y) 

3. 要使用指定的預設值： 

d = defaultdict(lambda :False)

參考資料：

https://docs.python.org/3/library/collections.html#collections.defaultdict