lessons/互动程序/02-强连通与双连通/00-从共享房间到圆方树.py

#!/usr/bin/env python3
"""课前零食：从删点实验到圆方树的可操作小黑板。"""

from __future__ import annotations

from collections import deque


VERTICES = tuple("ABCDEFG")
EDGES = (
    ("A", "B"),
    ("B", "C"),
    ("C", "A"),
    ("C", "D"),
    ("D", "E"),
    ("E", "C"),
    ("C", "F"),
    ("F", "G"),
)


def make_graph() -> dict[str, list[tuple[str, int]]]:
    graph = {vertex: [] for vertex in VERTICES}
    for edge_id, (u, v) in enumerate(EDGES):
        graph[u].append((v, edge_id))
        graph[v].append((u, edge_id))
    return graph


GRAPH = make_graph()


def tarjan_blocks(with_trace: bool = False) -> tuple[list[list[int]], dict[str, int], dict[str, int], list[str]]:
    """返回按原边编号排序的点双边块、dfn、low 和可读日志。"""
    dfn: dict[str, int] = {}
    low: dict[str, int] = {}
    edge_stack: list[int] = []
    blocks: list[list[int]] = []
    trace: list[str] = []
    timer = 0

    def say(message: str) -> None:
        if with_trace:
            trace.append(message)

    def dfs(u: str, parent_edge: int | None) -> None:
        nonlocal timer
        timer += 1
        dfn[u] = low[u] = timer
        say(f"进入 {u}：dfn=low={timer}")
        for v, edge_id in GRAPH[u]:
            if edge_id == parent_edge:
                continue
            if v not in dfn:
                edge_stack.append(edge_id)
                say(f"  压边 {u}-{v}；栈={edge_names(edge_stack)}")
                dfs(v, edge_id)
                low[u] = min(low[u], low[v])
                say(f"  {v} 返回 {u}：low[{u}] 更新为 {low[u]}")
                if low[v] >= dfn[u]:
                    block: list[int] = []
                    while True:
                        popped = edge_stack.pop()
                        block.append(popped)
                        if popped == edge_id:
                            break
                    say(
                        f"  low[{v}]={low[v]} ≥ dfn[{u}]={dfn[u]}："
                        f"弹出 {edge_names(block)}，封成一个点双块"
                    )
                    blocks.append(block)
            elif dfn[v] < dfn[u]:
                edge_stack.append(edge_id)
                low[u] = min(low[u], dfn[v])
                say(
                    f"  看见返祖边 {u}-{v}：压栈，"
                    f"low[{u}] 更新为 {low[u]}"
                )

    for start in VERTICES:
        if start not in dfn:
            dfs(start, None)

    blocks.sort(key=min)
    return blocks, dfn, low, trace


def edge_name(edge_id: int) -> str:
    u, v = EDGES[edge_id]
    return f"{u}-{v}"


def edge_names(edge_ids: list[int]) -> str:
    return "[" + ", ".join(edge_name(edge_id) for edge_id in edge_ids) + "]"


def block_members(block: list[int]) -> list[str]:
    return sorted({vertex for edge_id in block for vertex in EDGES[edge_id]})


def build_block_cut_tree(blocks: list[list[int]]) -> dict[str, list[str]]:
    tree: dict[str, list[str]] = {vertex: [] for vertex in VERTICES}
    for index, block in enumerate(blocks, start=1):
        square = f"Q{index}"
        tree[square] = []
        for vertex in block_members(block):
            tree[vertex].append(square)
            tree[square].append(vertex)
    return tree


def components_after_delete(removed: str) -> list[list[str]]:
    remaining = set(VERTICES) - {removed}
    components: list[list[str]] = []
    while remaining:
        start = min(remaining)
        queue = deque([start])
        remaining.remove(start)
        component = [start]
        while queue:
            u = queue.popleft()
            for v, _ in GRAPH[u]:
                if v in remaining and v != removed:
                    remaining.remove(v)
                    queue.append(v)
                    component.append(v)
        components.append(sorted(component))
    return components


def tree_path(tree: dict[str, list[str]], start: str, target: str) -> list[str] | None:
    if start not in tree or target not in tree:
        return None
    parent = {start: None}
    queue = deque([start])
    while queue:
        u = queue.popleft()
        if u == target:
            break
        for v in tree[u]:
            if v not in parent:
                parent[v] = u
                queue.append(v)
    if target not in parent:
        return None
    path: list[str] = []
    current: str | None = target
    while current is not None:
        path.append(current)
        current = parent[current]
    return list(reversed(path))


def show(blocks: list[list[int]], dfn: dict[str, int], low: dict[str, int]) -> None:
    print("\n原图边：", ", ".join(edge_name(edge_id) for edge_id in range(len(EDGES))))
    print("DFS 账本：", "  ".join(f"{u}: dfn={dfn[u]}, low={low[u]}" for u in VERTICES))
    print("点双块（按原边编号排序后命名）：")
    for index, block in enumerate(blocks, start=1):
        print(f"  Q{index}: 边 {edge_names(block)}；成员 {block_members(block)}")
    tree = build_block_cut_tree(blocks)
    print("圆方树邻接表：")
    for node in list(VERTICES) + [f"Q{i}" for i in range(1, len(blocks) + 1)]:
        print(f"  {node}: {' '.join(tree[node])}")


def warmup() -> None:
    print("=== 任务 0：先当删点的暴力程序 ===")
    try:
        input("先预测删掉 C 后会有几块；写在纸上后按回车： ")
    except EOFError:
        pass
    print("核对：删 C 后是 {A,B}、{D,E}、{F,G} 三块。")
    try:
        input("再猜：谁可以同时属于 ABC 和 CDE 两个结实小团？按回车： ")
    except EOFError:
        pass
    print("核对：C。圆方树不复制 C，而是给每个块新建方点。")


def main() -> None:
    blocks, dfn, low, trace = tarjan_blocks(with_trace=True)
    tree = build_block_cut_tree(blocks)
    print("圆方树小实验室：所有边都是固定的小图，目标是看清状态。")
    warmup()
    show(blocks, dfn, low)
    print("\n命令：show；delete C；path A G；trace；q。")
    while True:
        try:
            raw = input("\n> ").strip()
        except EOFError:
            raw = "q"
        if not raw or raw in {"q", "quit", "exit"}:
            return
        parts = raw.split()
        if parts == ["show"]:
            show(blocks, dfn, low)
        elif parts == ["trace"]:
            print("\nTarjan 边栈日志：")
            for line in trace:
                print(line)
        elif len(parts) == 2 and parts[0] == "delete" and parts[1] in VERTICES:
            removed = parts[1]
            components = components_after_delete(removed)
            print(f"删 {removed} 后：", "  ".join("{" + ",".join(c) + "}" for c in components))
            print("连通块数：", len(components))
        elif len(parts) == 3 and parts[0] == "path":
            path = tree_path(tree, parts[1], parts[2])
            if path is None:
                print("节点名应为 A..G 或 Q1..Q4。")
            else:
                print("圆方树唯一路径：", " → ".join(path))
                cuts = [node for node in path if node in VERTICES and len(tree[node]) > 1]
                print("路径中的割点候选：", cuts or "无")
        else:
            print("小提示：试试 delete C、path A G、trace。")


if __name__ == "__main__":
    main()