Bipartite Check二分圖判定

from collections import deque


def bipartite_colors(adj):
    """BFS 兩色染色。是二分圖回傳每個節點的顏色（0 或 1），否則回傳 None"""
    n = len(adj)
    color = [-1] * n                          # -1 表示還沒塗色
    for s in range(n):                        # 圖可能不連通：每個連通分量各起一次
        if color[s] != -1:
            continue
        color[s] = 0                          # 新分量的起點塗哪一色都可以
        queue = deque([s])
        while queue:
            u = queue.popleft()
            for v in adj[u]:
                if color[v] == -1:
                    color[v] = 1 - color[u]   # 鄰居被逼成相反色，沒有選擇
                    queue.append(v)
                elif color[v] == color[u]:
                    return None               # 兩端同色：圖裡有奇環
    return color


def find_odd_cycle(adj):
    """不是二分圖時回傳一個奇環（依序列出節點）當作證據；是二分圖回傳 None"""
    n = len(adj)
    depth, parent = [-1] * n, [-1] * n
    for s in range(n):
        if depth[s] != -1:
            continue
        depth[s] = 0
        queue = deque([s])
        while queue:
            u = queue.popleft()
            for v in adj[u]:
                if depth[v] == -1:
                    depth[v], parent[v] = depth[u] + 1, u
                    queue.append(v)
                elif depth[v] % 2 == depth[u] % 2:  # 顏色就是 BFS 層數的奇偶
                    a, b = [u], [v]
                    while a[-1] != b[-1]:           # 較深的一端先往上爬，直到會合
                        if depth[a[-1]] >= depth[b[-1]]:
                            a.append(parent[a[-1]])
                        else:
                            b.append(parent[b[-1]])
                    return a + b[-2::-1]            # u → 會合點 → v，再由邊 v–u 閉合
    return None


def first_conflict_edge(n, edges):
    """邊一條一條加入：回傳第一條讓圖不再是二分圖的邊的索引，沒有就回傳 -1"""
    parent = list(range(2 * n))               # x 代表「x 這一側」，x + n 代表「x 的對面」

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

    for i, (u, v) in enumerate(edges):
        if find(u) == find(v):                # u、v 早就被逼到同一側
            return i
        parent[find(u)] = find(v + n)         # u 和 v 的對面同側
        parent[find(v)] = find(u + n)         # v 和 u 的對面同側
    return -1


def build(n, edges):
    adj = [[] for _ in range(n)]
    for u, v in edges:
        adj[u].append(v)
        adj[v].append(u)
    return adj


if __name__ == "__main__":
    # 與互動示範同一張圖：A..F 編號為 0..5
    ok = [(0, 1), (0, 3), (1, 2), (2, 3), (2, 4), (3, 5), (4, 5)]
    odd = [(0, 1), (0, 3), (1, 2), (2, 3), (2, 4), (3, 4), (4, 5)]
    print(bipartite_colors(build(6, ok)))    # [0, 1, 0, 1, 1, 0]
    print(bipartite_colors(build(6, odd)))   # None
    print(["ABCDEF"[x] for x in find_odd_cycle(build(6, odd))])  # ['C', 'B', 'A', 'D', 'E']
    print(first_conflict_edge(6, odd))       # 5：加入 D–E 時，C–D–E 成了三角形