你可以把Union Find想成一個樹狀結構
Find是找樹根, Union是把樹合併成一棵
初始每個點都是一棵樹, 所以root是自己
## Find: 回傳該點的樹根
Basic: 一直檢查父節點, 直到找到樹的root
```python
def find(self, x):
while x != self.root[x]:
x = self.root[x]
return x
```
Optimized: path compression
查找root的時候, 順便把樹扁平化 -> 父節點都直接指向root
```python
def find(self, x):
if x != self.root[x]:
self.root[x] = self.find(self.root[x])
return self.root[x]
```
## Union: 如果兩點在不同樹上, 就把樹合併
Basic:
兩個點如果連接的話, 表示兩點在同一棵樹上(樹根相同)
如果不相連, 就直接把root_y 的父節點設為 root_x
```python
def union(self, x, y):
root_x = self.find(x)
root_y = self.find(y)
if root_x != root_y:
self.root[root_y] = root_x
```
Optimized: Union by Rank
就..比較小的接在大樹下
```python
def union(self, x, y):
root_x = self.find(x)
root_y = self.find(y)
if root_x == root_y:
return False
if self.rank[root_x] >= self.rank[root_y]:
self.rank[root_x] += self.rank[root_y]
self.root[root_y] = root_x
else:
self.rank[root_y] += self.rank[root_x]
self.root[root_x] = root_y
return True
```
整個合起來 Template大概是這樣:
```python
class UnionFind:
def __init__(self, n):
self.root = list(range(n))
self.rank = [1] * n
def find(self, x):
if self.root[x] != x:
self.root[x] = self.find(self.root[x])
return self.root[x]
def union(self, x, y):
rx, ry = self.find(x), self.find(y)
if rx == ry:
return 0
if self.rank[rx] >= self.rank[ry]:
self.rank[rx] += self.rank[ry]
self.root[ry] = rx
else:
self.rank[ry] += self.rank[rx]
self.root[rx] = ry
return 1
```