拓扑排序与依赖关系

import sys
from collections import defaultdict, deque

edges = set()                              # 同一条「主 次」关系出现两次只算一条
for line in sys.stdin.read().split("\n"):
    parts = line.split()
    if len(parts) == 2:
        edges.add((parts[0], parts[1]))    # 主告警 → 次告警

adj = defaultdict(list)
indeg = defaultdict(int)
nodes = set()
for a, b in edges:
    adj[a].append(b)
    indeg[b] += 1
    nodes.add(a)
    nodes.add(b)

multi = sorted(v for v in nodes if indeg[v] > 1)   # 情况 1：同一个次告警有多个主告警
if multi:
    print(f"[1001,({','.join(multi)})]")   # 两种情况同时存在时输出检查码最小的 1001
else:
    q = deque(v for v in nodes if indeg[v] == 0)
    done = 0
    while q:                               # Kahn：拓扑序长度 < 节点数 ⇔ 有环
        u = q.popleft()
        done += 1
        for v in adj[u]:
            indeg[v] -= 1
            if indeg[v] == 0:
                q.append(v)
    print("[1002,cycle]" if done < len(nodes) else "[1003,Verified]")

自测建议：题面两组示例、第 05 节三个自拟输入。重复行按题意「同一个告警是否存在多个主告警」去重；题目页参考题解没有单独处理重复行，判题数据以题目页为准。

import sys
from collections import defaultdict, deque

data = sys.stdin.read().split()
n = int(data[0])
vals = [int(x) for x in data[1:1 + 2 * n]]

adj = defaultdict(list)
indeg = defaultdict(int)
nodes = set()
for i in range(0, 2 * n, 2):
    a, b = vals[i], vals[i + 1]            # a → b
    adj[a].append(b)
    indeg[b] += 1
    nodes.add(a)
    nodes.add(b)

q = deque(v for v in nodes if indeg[v] == 0)
done = 0
indeg_left = dict(indeg)
while q:
    u = q.popleft()
    done += 1
    for v in adj[u]:
        indeg_left[v] -= 1
        if indeg_left[v] == 0:
            q.append(v)

if done < len(nodes):                      # 有环
    print(-1)
else:
    heads = [v for v in nodes if indeg[v] == 0]          # 入度 0 = 头（题目保证唯一）
    tails = sorted(v for v in nodes if not adj[v])       # 出度 0 = 尾（可能多个，从小到大）
    print(heads[0], *tails)

自测建议：题面示例（输出 1 4）、有环（输出 -1）、编号不连续且多个尾（3 / 1 2 1 3 3 5 → 1 2 5）。题面写 N ≥ 0，但 N = 0（没有任何边）时「唯一头节点」无从谈起，本程序不处理这种输入；题目页若有此类用例以题目页为准。

import sys
from collections import defaultdict, deque

pairs = sys.stdin.read().split()
adj = defaultdict(list)                    # 被依赖者 → 依赖它的任务
indeg = defaultdict(int)
nodes = set()
for token in pairs:
    a, b = token.split("->")               # A->B：A 依赖 B，先做 B 再做 A，边 B → A
    adj[b].append(a)
    indeg[a] += 1
    nodes.add(a)
    nodes.add(b)

order = sorted(v for v in nodes if indeg[v] == 0)   # 一开始就能执行的任务，按名字排序
q = deque(order)
while q:
    freed = []                             # 这一轮执行完后新变成可执行的任务
    for _ in range(len(q)):                # 同一轮里的任务同时执行
        u = q.popleft()
        for v in adj[u]:
            indeg[v] -= 1
            if indeg[v] == 0:
                freed.append(v)
    freed.sort()                           # 同一轮新可执行的任务按字母序
    order.extend(freed)
    q.extend(freed)
print(*order)

自测建议：题面两组示例（A E B C D、B A C）、第 07 节第二组（A Y B C Z）。

from collections import deque, defaultdict

def topo_order(n, edges):
    adj = defaultdict(list)
    indeg = [0] * n
    for a, b in edges:                    # a → b：先 a 后 b
        adj[a].append(b)
        indeg[b] += 1
    q = deque(v for v in range(n) if indeg[v] == 0)
    order = []
    while q:
        u = q.popleft()
        order.append(u)
        for v in adj[u]:
            indeg[v] -= 1
            if indeg[v] == 0:             # 减到 0 的那一刻入队
                q.append(v)
    return order if len(order) == n else None   # 拓扑序长度 < 节点数 ⇔ 有环

assert topo_order(4, [(0, 1), (0, 2), (1, 3), (2, 3)]) in ([0, 1, 2, 3], [0, 2, 1, 3])
assert topo_order(2, [(0, 1), (1, 0)]) is None   # 成环
assert topo_order(1, [(0, 0)]) is None           # 自环也是环：入度天然 ≥ 1，永远进不了队列
assert topo_order(4, [(0, 1), (0, 2), (1, 3), (2, 3), (3, 0)]) is None   # 补一条 3→0 后有环
assert topo_order(3, []) == [0, 1, 2]            # 无边：全部入度 0

五条断言覆盖：4 节点两种合法序、二元环、自环、补边成环、无边。自环不需要特判：入度天然 ≥ 1，永远进不了队列，长度判据一样能抓住。