並查集（Union-Find） 判定環

 利用 並查集（Union-Find） 判定無向圖是否有環。

---

問題描述

給定一個無向圖，其頂點數為 (n)，邊數為 (m)。
檢查該圖中是否存在環。

---

解法

我們可以利用並查集來判定圖中是否有環：

1. 將每條邊的兩個端點進行連接（合併）。
2. 如果某條邊的兩個端點已經屬於同一集合，則說明這條邊的加入會形成環。

---

程式碼實現

class UnionFind:
    def __init__(self, n):
        """初始化並查集，每個節點一開始是自己的父節點"""
        self.parent = list(range(n))
        self.rank = [0] * 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:  # 如果兩個節點不在同一集合
            if self.rank[root_x] > self.rank[root_y]:
                self.parent[root_y] = root_x
            elif self.rank[root_x] < self.rank[root_y]:
                self.parent[root_x] = root_y
            else:
                self.parent[root_y] = root_x
                self.rank[root_x] += 1

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


def detect_cycle(edges, n):
    """
    判定圖中是否有環
    :param edges: 邊列表，每條邊為 (u, v)
    :param n: 節點數
    :return: True 如果有環，False 否則
    """
    uf = UnionFind(n)

    for u, v in edges:
        if uf.is_connected(u, v):  # 如果兩個節點已經連通，則形成環
            return True
        uf.union(u, v)

    return False


# 測試資料
n = 5  # 節點數
edges = [
    (0, 1),
    (1, 2),
    (2, 3),
    (3, 4),
    (4, 1)  # 這條邊會形成環
]

# 檢查是否有環
print("圖是否有環:", detect_cycle(edges, n))

---

程式輸出

對於上面提供的測試資料，輸出結果為：

圖是否有環: True

---

程式說明

核心邏輯

1. 初始化時，所有頂點都是獨立的集合。
2. 每次處理一條邊 ((u, v)) 時：
   • 如果 (u) 和 (v) 已經在同一集合，則形成環。
   • 如果 (u) 和 (v) 不在同一集合，則合併它們。
3. 如果遍歷所有邊後未發現環，則圖中無環。

---

適用範圍

• 只適用於 無向圖 的環檢查。
• 若處理 有向圖，需使用其他方法（如 DFS）。

測試資料

測試資料 1

輸入：

n = 4
edges = [
    (0, 1),
    (1, 2),
    (2, 3)
]

輸出：

圖是否有環: False

---

測試資料 2

輸入：

n = 5
edges = [
    (0, 1),
    (1, 2),
    (2, 0),
    (3, 4)
]

輸出：

圖是否有環: True

---

優點

• 並查集結構簡單，適合處理大規模的連通性問題。
• 對於稀疏圖（邊數少於頂點數的平方），效率極高。