谁在等谁

按等待图：A 占 L1 想要 L2、B 占 L2 想要 L1，waitfor 里 A 在等谁？（打印整个 waitfor 的 A 项）

贯穿本节的等待图模型（判题机不靠时序，这是死锁的确定模型）：holds={锁: 持有它的线程}、wants={线程: 想要的锁}。想要的锁被别人占着就连一条等待边。waitfor 交回等待边 {等的人: 被等的人}，find_cycle 交回环上的线程（没环 []），deadlocked 判有没有死锁，blocked 数几个在等；victim 从环里挑一个当牺牲者、after_abort 中止它后还有没有环、cycle_len 环有多长。

def waitfor(holds, wants):
    # holds: {锁: 持有它的线程}; wants: {线程: 它想要的锁}
    # 建等待边：线程 T 想要的锁被 U 持着 -> T 等 U
    edges = {}
    for t, lk in wants.items():
        if lk in holds and holds[lk] != t:
            edges[t] = holds[lk]
    return edges


def find_cycle(edges):
    # 有环就交回环上的线程（按遇到顺序），没有交回 []
    for start in edges:
        seen = []
        cur = start
        while cur in edges and cur not in seen:
            seen.append(cur)
            cur = edges[cur]
        if cur in seen:
            return seen[seen.index(cur):]
    return []


def deadlocked(holds, wants):
    return bool(find_cycle(waitfor(holds, wants)))


def blocked(holds, wants):
    # 有几个线程在等锁（等待图里有出边的）
    return len(waitfor(holds, wants))


def victim(edges):
    # 恢复：从环里挑一个当牺牲者（取环上第一个），交回它的名字；没环交回 ""
    c = find_cycle(edges)
    return c[0] if c else ""


def after_abort(edges, t):
    # 中止线程 t、去掉它的等待边后，还有没有环
    e = {k: v for k, v in edges.items() if k != t}
    return bool(find_cycle(e))


def cycle_len(edges):
    # 环有多长（几个线程绕成一圈）；没环 0
    return len(find_cycle(edges))

holds = {"L1": "A", "L2": "B"}
wants = {"A": "L2", "B": "L1"}
print(waitfor(holds, wants)["A"])