並查集（Union-Find）

 並查集（Union-Find） 說明和例子

---

並查集是什麼？

並查集 是一種用來解決「分組問題」的工具，特別是幫助我們回答：

1. 某兩個東西是不是在同一組？
2. 怎麼把兩個東西分到同一組？

---

例子

想像有 10 個同學站成一排，每個人開始時自己是一組，互相不認識。我們有兩種操作：

1. 合併（Union）：讓兩個同學成為朋友，分到同一組。
2. 查詢（Find）：問兩個同學是否已經是朋友（在同一組）。

---

基本操作

1. 查詢操作（Find）

每個組都有一個「代表人」（類似於隊長）。
我們可以通過 Find 操作 找到某個人的隊長。

---

2. 合併操作（Union）

如果兩個人不在同一組，就把其中一個人的隊長變成另一個人的隊長，讓兩組合併。

---

程式碼

以下是簡單的 Python 程式來實現並查集：

class UnionFind:
    def __init__(self, n):
        """初始化，每個人開始時自己是一組"""
        self.parent = list(range(n))  # 每個人的父節點一開始是自己

    def find(self, x):
        """找到 x 的隊長"""
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])  # 路徑壓縮，讓隊伍更扁平
        return self.parent[x]

    def union(self, x, y):
        """把 x 和 y 分到同一組"""
        root_x = self.find(x)
        root_y = self.find(y)
        if root_x != root_y:  # 如果不在同一組，合併
            self.parent[root_y] = root_x

    def is_connected(self, x, y):
        """檢查 x 和 y 是否在同一組"""
        return self.find(x) == self.find(y)

---

例子

問題：

有 5 個人 ( {0, 1, 2, 3, 4} )。
最開始每個人都是自己一組。
進行以下操作：

1. 把 0 和 1 分到一組。
2. 把 1 和 2 分到一組。
3. 問 0 和 2 是否在同一組。
4. 問 0 和 3 是否在同一組。

程式執行：

# 初始化 5 個人
uf = UnionFind(5)

# 操作
uf.union(0, 1)  # 把 0 和 1 分到一組
uf.union(1, 2)  # 把 1 和 2 分到一組

# 查詢
print(uf.is_connected(0, 2))  # True，因為 0 和 2 已經連通
print(uf.is_connected(0, 3))  # False，因為 0 和 3 不在同一組

輸出：

True
False

---

視覺化解釋

1. 初始化時，每個人都是自己一組：

   0   1   2   3   4
   

2. 執行 uf.union(0, 1)，0 和 1 成為朋友：

   0 - 1   2   3   4
   

3. 執行 uf.union(1, 2)，0、1、2 成為朋友：

   0 - 1 - 2   3   4
   

4. 查詢 uf.is_connected(0, 2)，答案是 True，因為 0 和 2 已經連通。

---

總結

1. 並查集是一種 快速分組的工具。
2. 最重要的操作是：
   • find(x)：找到某個人的組代表。
   • union(x, y)：把兩個人分到同一組。
3. 適用場景：
   • 檢查圖中是否連通。
   • 檢查是否形成環（比如圖的最小生成樹）。