Cycle Detection環偵測

WHITE, GRAY, BLACK = 0, 1, 2


def find_directed_cycle(n, edges):
    """有向圖：三色 DFS。回傳環上的節點（頭尾相同），沒有環回傳 None"""
    adj = [[] for _ in range(n)]
    for u, v in edges:
        adj[u].append(v)
    color = [WHITE] * n
    path = []                                # 目前的呼叫堆疊

    def dfs(u):
        color[u] = GRAY                      # 進入：u 在路徑上
        path.append(u)
        for v in adj[u]:
            if color[v] == GRAY:             # 回邊：v 還在路徑上
                return path[path.index(v):] + [v]
            if color[v] == WHITE:
                cycle = dfs(v)
                if cycle:
                    return cycle
        path.pop()
        color[u] = BLACK                     # 離開：從 u 出發回不到路徑上
        return None

    for s in range(n):                       # 圖可能不連通，每個白色節點都要當起點
        if color[s] == WHITE:
            cycle = dfs(s)
            if cycle:
                return cycle
    return None


def has_undirected_cycle(n, edges):
    """無向圖：併查集。邊的兩端已經同群，這條邊就會閉合成環"""
    parent = list(range(n))
    size = [1] * n

    def find(x):
        while parent[x] != x:
            parent[x] = parent[parent[x]]    # 路徑減半
            x = parent[x]
        return x

    for u, v in edges:
        ru, rv = find(u), find(v)
        if ru == rv:
            return True
        if size[ru] < size[rv]:              # 小樹接到大樹底下
            ru, rv = rv, ru
        parent[rv] = ru
        size[ru] += size[rv]
    return False


def has_undirected_cycle_dfs(n, edges):
    """無向圖的 DFS 版：已拜訪的鄰居、而且不是剛走過來的那條邊，就是環"""
    adj = [[] for _ in range(n)]
    for i, (u, v) in enumerate(edges):
        adj[u].append((v, i))
        adj[v].append((u, i))
    seen = [False] * n

    def dfs(u, via):                         # via：走到 u 用的邊編號
        seen[u] = True
        for v, i in adj[u]:
            if i == via:                     # 比對邊編號而不是父節點，平行邊才不會漏
                continue
            if seen[v] or dfs(v, i):
                return True
        return False

    return any(not seen[s] and dfs(s, -1) for s in range(n))


if __name__ == "__main__":
    # 與互動示範相同的圖，A..F 編號成 0..5
    directed = [(0, 1), (0, 5), (1, 2), (1, 3), (3, 4), (4, 1), (5, 4)]
    print(find_directed_cycle(6, directed))                      # [1, 3, 4, 1]，即 B → D → E → B
    print(find_directed_cycle(4, [(0, 1), (0, 2), (1, 3), (2, 3)]))  # None（菱形：3 被走到兩次，但沒有環）
    undirected = [(0, 1), (1, 2), (0, 5), (2, 3), (5, 4), (3, 4), (1, 3)]
    print(has_undirected_cycle(6, undirected))                   # True（第 6 條 D – E 閉合成環）
    print(has_undirected_cycle(6, undirected[:5]))               # False（前 5 條邊是一棵樹）
    print(has_undirected_cycle_dfs(6, undirected[:5]))           # False
    print(has_undirected_cycle_dfs(2, [(0, 1), (0, 1)]))         # True（兩條平行邊也是環）