lessons/互动程序/09-基环树/00-树多长出一条边.py

#!/usr/bin/env python3
"""课前零食：用队列剥离无向基环树或函数图的挂树。"""

from __future__ import annotations

from collections import defaultdict, deque


UNDIRECTED = [("A", "B"), ("B", "C"), ("C", "A"), ("B", "D"), ("D", "E"), ("C", "F"), ("C", "G")]
FUNCTIONAL = {"A": "B", "B": "C", "C": "A", "D": "C", "E": "D", "F": "E"}


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


def undirected_lab() -> None:
    graph: dict[str, list[str]] = defaultdict(list)
    for u, v in UNDIRECTED:
        graph[u].append(v)
        graph[v].append(u)
    degree = {u: len(graph[u]) for u in graph}
    removed = {u: False for u in graph}
    queue: deque[str] = deque(u for u in graph if degree[u] == 1)
    print("边：", ", ".join(f"{u}-{v}" for u, v in UNDIRECTED))
    print("初始叶子：", list(queue))
    while queue:
        u = queue.popleft()
        removed[u] = True
        print(f"删掉叶子 {u}，它一定不在环上。")
        for v in graph[u]:
            if not removed[v]:
                degree[v] -= 1
                print(f"  {v} 的剩余度数变为 {degree[v]}")
                if degree[v] == 1:
                    queue.append(v)
                    print(f"  {v} 新成为叶子，入队。")
    print("剩余环点：", sorted(u for u in graph if not removed[u]))


def functional_lab() -> None:
    indegree = {u: 0 for u in FUNCTIONAL}
    for v in FUNCTIONAL.values():
        indegree[v] += 1
    queue: deque[str] = deque(u for u, value in indegree.items() if value == 0)
    removed: set[str] = set()
    print("箭头：", ", ".join(f"{u}->{v}" for u, v in FUNCTIONAL.items()))
    print("初始入度 0：", list(queue))
    while queue:
        u = queue.popleft()
        removed.add(u)
        v = FUNCTIONAL[u]
        indegree[v] -= 1
        print(f"删 {u}，使 {v} 入度变为 {indegree[v]}")
        if indegree[v] == 0:
            queue.append(v)
            print(f"  {v} 也不可能在环上，入队。")
    print("剩余有向环点：", sorted(set(FUNCTIONAL) - removed))


def main() -> None:
    choice = ask("选择 u=无向基环树，f=函数图（回车为 u）： ", "u").lower()
    if choice == "f":
        functional_lab()
    else:
        undirected_lab()


if __name__ == "__main__":
    main()