lessons/互动程序/02-强连通与双连通/00-从互相绕路到缩点.py

#!/usr/bin/env python3
"""课前零食：在小图上追踪 SCC、桥和割点。"""

from __future__ import annotations

from collections import defaultdict


DIRECTED = [("A", "B"), ("B", "C"), ("C", "A"), ("C", "D"), ("D", "E"), ("E", "D"), ("E", "F")]
UNDIRECTED = [("A", "B"), ("B", "C"), ("C", "A"), ("C", "D"), ("D", "E"), ("E", "F"), ("F", "D")]


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


def scc_lab() -> None:
    graph: dict[str, list[str]] = defaultdict(list)
    reverse: dict[str, list[str]] = defaultdict(list)
    vertices = set()
    for u, v in DIRECTED:
        graph[u].append(v)
        reverse[v].append(u)
        vertices.update((u, v))
    finish: list[str] = []
    seen: set[str] = set()

    def first_dfs(u: str) -> None:
        seen.add(u)
        print(f"原图进入 {u}")
        for v in graph[u]:
            if v not in seen:
                first_dfs(v)
        finish.append(u)
        print(f"  {u} 的后继都处理完，完成序列：{finish}")

    print("\n原图边：", ", ".join(f"{u}->{v}" for u, v in DIRECTED))
    for u in sorted(vertices):
        if u not in seen:
            first_dfs(u)
    print("\n反向完成顺序：", list(reversed(finish)))
    assigned: set[str] = set()
    groups: list[list[str]] = []

    def second_dfs(u: str, group: list[str]) -> None:
        assigned.add(u)
        group.append(u)
        for v in reverse[u]:
            if v not in assigned:
                second_dfs(v, group)

    for u in reversed(finish):
        if u not in assigned:
            group: list[str] = []
            second_dfs(u, group)
            groups.append(sorted(group))
            print("反图收下一团：", sorted(group))
    print("缩点后只剩单向关系；团内部的绕路已经不必重复计算。")


def fragility_lab() -> None:
    graph: dict[str, list[tuple[str, int]]] = defaultdict(list)
    vertices = set()
    for edge_id, (u, v) in enumerate(UNDIRECTED):
        graph[u].append((v, edge_id))
        graph[v].append((u, edge_id))
        vertices.update((u, v))
    dfn: dict[str, int] = {}
    low: dict[str, int] = {}
    bridges: list[tuple[str, str]] = []
    cuts: set[str] = set()
    timer = 0

    def dfs(u: str, parent_edge: int | None) -> None:
        nonlocal timer
        timer += 1
        dfn[u] = low[u] = timer
        children = 0
        for v, edge_id in graph[u]:
            if edge_id == parent_edge:
                continue
            if v not in dfn:
                children += 1
                dfs(v, edge_id)
                low[u] = min(low[u], low[v])
                print(f"回到 {u}：孩子 {v} 的 low={low[v]}，所以 low[{u}]={low[u]}")
                if low[v] > dfn[u]:
                    bridges.append((u, v))
                if parent_edge is not None and low[v] >= dfn[u]:
                    cuts.add(u)
            else:
                low[u] = min(low[u], dfn[v])
                print(f"{u} 看见返祖/已访问边到 {v}：low[{u}] 更新为 {low[u]}")
        if parent_edge is None and children >= 2:
            cuts.add(u)

    print("\n无向图边：", ", ".join(f"{u}-{v}" for u, v in UNDIRECTED))
    for u in sorted(vertices):
        if u not in dfn:
            dfs(u, None)
    print("\ndfn：", dfn)
    print("low：", low)
    print("桥：", bridges or "没有")
    print("割点：", sorted(cuts) or "没有")


def main() -> None:
    print("连通小实验室：1=SCC 缩点，2=桥与割点。")
    choice = ask("选择（直接回车为 1）： ", "1")
    if choice == "2":
        fragility_lab()
    else:
        scc_lab()


if __name__ == "__main__":
    main()