每加入一条大小关系就重跑拓扑排序，用队列分支数判断唯一序列并用处理点数判断矛盾。
OJ: luogu
题目 ID: P1347
难度:普及/提高-
标签:拓扑排序DAG唯一性python
日期: 2026-07-16 18:42
题意
依次给出 A<B 形式的关系。求最早在第几条关系后能唯一确定全部顺序，或最早发现矛盾；若所有关系处理完仍不能确定，则输出无法确定。
思路
把 A<B 建成有向边 A -> B。每加入一条新边就对当前图做一次 Kahn 拓扑排序：
- 最终处理点数小于
n，说明有环，当前关系产生矛盾； - 每一步零入度队列都恰好只有一个点，说明每个位置都没有第二种选择，拓扑序唯一；
- 某一步队列有多个点，当前关系还不能唯一确定顺序。
题目要求报告首次确定或首次矛盾，所以每加入一条关系都检查，并在得到结论时立即结束。重复关系不能再次增加入度，代码用邻接矩阵先判重。
Python 知识
bytearray(n)作为邻接矩阵的一行，n<=26时紧凑且判重直接。indegree.copy()保留原入度，让每次试跑拓扑排序互不影响。enumerate(relations,1)同时得到关系和从1开始的输入序号。"".join(chr(node+65) for node in order)把编号转回大写字母序列。/home/rainboy/mycode/hugo-blog/content/program_language/python/collections_toolkit.md：deque拓扑队列。/home/rainboy/mycode/hugo-blog/content/program_language/python/generator_expression.md：生成器拼接答案。
代码
python
import sys
from collections import deque
def topological_status(graph, indegree, n):
degree = indegree.copy()
queue = deque(node for node in range(n) if degree[node] == 0)
order = []
unique = True
while queue:
if len(queue) > 1:
unique = False
node = queue.popleft()
order.append(node)
for neighbor in range(n):
if graph[node][neighbor]:
degree[neighbor] -= 1
if degree[neighbor] == 0:
queue.append(neighbor)
if len(order) < n:
return "inconsistent", order
return ("determined" if unique else "unknown"), order
def main():
read = sys.stdin.buffer.readline
n, m = map(int, read().split())
relations = [read().strip() for _ in range(m)]
graph = [bytearray(n) for _ in range(n)]
indegree = [0] * n
for index, relation in enumerate(relations, 1):
smaller, larger = relation[0] - 65, relation[2] - 65
if not graph[smaller][larger]:
graph[smaller][larger] = 1
indegree[larger] += 1
status, order = topological_status(graph, indegree, n)
if status == "inconsistent":
print(f"Inconsistency found after {index} relations.")
return
if status == "determined":
sequence = "".join(chr(node + 65) for node in order)
print(f"Sorted sequence determined after {index} relations: {sequence}.")
return
print("Sorted sequence cannot be determined.")
if __name__ == "__main__":
main()cpp
/**
* P1347 排序
* Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
* rbook: -> https://rbook.roj.ac.cn
* rainboy的学习导航网站: https://idx.roj.ac.cn
* create_at: 2026-07-27 00:00
* update_at: 2026-07-27 00:00
*/
#include <bits/stdc++.h>
using namespace std;
int n, m;
int graph[26][26]; // 邻接矩阵
int indeg[26]; // 入度
// 返回状态：0=不确定 1=确定 2=矛盾
int topo(char order[]) {
int deg[26], idx = 0;
memcpy(deg, indeg, sizeof(deg));
queue<int> q;
for (int i = 0; i < n; ++i)
if (deg[i] == 0) q.push(i);
bool unique = true;
while (!q.empty()) {
if (q.size() > 1) unique = false;
int u = q.front(); q.pop();
order[idx++] = u + 'A';
for (int v = 0; v < n; ++v)
if (graph[u][v] && --deg[v] == 0) q.push(v);
}
order[idx] = '\0';
if (idx < n) return 2; // 有环 → 矛盾
return unique ? 1 : 0; // 唯一确定 or 尚不确定
}
int main() {
scanf("%d%d", &n, &m);
char rel[5];
for (int i = 1; i <= m; ++i) {
scanf("%s", rel);
int a = rel[0] - 'A', b = rel[2] - 'A';
if (!graph[a][b]) {
graph[a][b] = 1;
++indeg[b];
}
char ord[26];
int st = topo(ord);
if (st == 2) {
printf("Inconsistency found after %d relations.\n", i);
return 0;
}
if (st == 1 && i < m) {
// 确定后还需要验证后续关系不矛盾
// 但不能提前退出，因为后续可能矛盾
// 但是题目说：确定后可直接结束
printf("Sorted sequence determined after %d relations: %s.\n", i, ord);
return 0;
}
}
puts("Sorted sequence cannot be determined.");
return 0;
}复杂度
每条关系后做一次邻接矩阵拓扑排序，时间复杂度 n<=26，足够通过。
总结
拓扑排序不仅能判断有环，还能判断拓扑序是否唯一：观察每一步是否只有一个零入度选择即可。