lessons/互动程序/07-二分图/00-两支队伍与奇怪的圈.py

#!/usr/bin/env python3
"""课前零食：交替染色，并在冲突时给出一条奇环。"""

from __future__ import annotations

from collections import defaultdict, deque


GOOD = [("A", "B"), ("A", "D"), ("C", "B"), ("C", "D"), ("E", "F")]
BAD = [("A", "B"), ("B", "C"), ("C", "A"), ("C", "D")]


def ask(prompt: str, default: str) -> str:
    try:
        return input(prompt).strip() or default
    except EOFError:
        return default


def parse_edges(raw: str) -> list[tuple[str, str]]:
    result: list[tuple[str, str]] = []
    for token in raw.replace("，", ",").split(","):
        left, right = (part.strip() for part in token.split("-", 1))
        if not left or not right:
            raise ValueError("边应形如 A-B")
        result.append((left, right))
    return result


def odd_cycle(u: str, v: str, parent: dict[str, str | None]) -> list[str]:
    up: list[str] = []
    cursor: str | None = u
    while cursor is not None:
        up.append(cursor)
        cursor = parent[cursor]
    vp: list[str] = []
    cursor = v
    while cursor is not None:
        vp.append(cursor)
        cursor = parent[cursor]
    position = {vertex: index for index, vertex in enumerate(up)}
    common = next(vertex for vertex in vp if vertex in position)
    left = up[:position[common] + 1]
    right = vp[:vp.index(common)]
    return left + list(reversed(right)) + [u]


def color_graph(edges: list[tuple[str, str]]) -> None:
    graph: dict[str, list[str]] = defaultdict(list)
    for u, v in edges:
        graph[u].append(v)
        graph[v].append(u)
    color = {vertex: -1 for vertex in graph}
    parent: dict[str, str | None] = {}
    for start in sorted(graph):
        if color[start] != -1:
            continue
        color[start] = 0
        parent[start] = None
        queue: deque[str] = deque([start])
        print(f"\n从 {start} 染成 0 开始")
        while queue:
            u = queue.popleft()
            for v in graph[u]:
                if color[v] == -1:
                    color[v] = 1 - color[u]
                    parent[v] = u
                    queue.append(v)
                    print(f"  边 {u}-{v}：把 {v} 染成 {color[v]}")
                elif color[v] == color[u]:
                    cycle = odd_cycle(u, v, parent)
                    print(f"  冲突！{u} 与 {v} 都是颜色 {color[u]}。")
                    print("  一条奇环：", " -> ".join(cycle))
                    return
    left = sorted(vertex for vertex, value in color.items() if value == 0)
    right = sorted(vertex for vertex, value in color.items() if value == 1)
    print("\n可二染：左侧(0)=", left, "；右侧(1)=", right)
    print("每个连通分量可以整体交换左右两侧。")


def main() -> None:
    choice = ask("选择 g=可二染预设，b=奇环预设，c=自定义（回车为 g）： ", "g").lower()
    if choice == "b":
        edges = BAD
    elif choice == "c":
        try:
            edges = parse_edges(ask("输入边 A-B,B-C： ", "A-B,B-C,C-A"))
        except (ValueError, IndexError) as error:
            print(f"格式不对：{error}；改用奇环预设。")
            edges = BAD
    else:
        edges = GOOD
    print("边：", ", ".join(f"{u}-{v}" for u, v in edges))
    color_graph(edges)


if __name__ == "__main__":
    main()