2024 年第 41 题

题目描述

给定一个有向无环图 G，判断其拓扑序列是否唯一。

解题思路

利用拓扑排序的入度思想。

如果在拓扑排序过程中，任意一步都只有一个入度为 0 的顶点可选，那么拓扑序唯一；只要某一步同时出现两个及以上入度为 0 的顶点，就说明当前顶点可以交换顺序，拓扑序不唯一。

算法流程：

1. 先统计所有顶点入度。
2. 把当前所有入度为 0 的顶点放入队列。
3. 每次取出一个顶点时，检查队列长度：
   • 若长度大于 1，说明不唯一。
4. 删除该顶点的所有出边，并更新相邻顶点入度。
5. 重复直到结束。

手算示例

图：

A -> C
B -> C

初始入度：

in(A)=0, in(B)=0, in(C)=2

第一步就有两个入度为 0 的顶点 A 和 B，因此：

拓扑序不唯一
可行序列至少有：A B C 和 B A C

Python 实现

from collections import deque


def is_topo_order_unique(graph):
    """
    graph: 邻接表，graph[u] = [v1, v2, ...]
    顶点默认用 0..n-1 编号
    """
    n = len(graph)
    indegree = [0] * n

    for u in range(n):
        for v in graph[u]:
            indegree[v] += 1

    queue = deque([i for i in range(n) if indegree[i] == 0])
    visited = 0

    while queue:
        if len(queue) > 1:
            return False

        u = queue.popleft()
        visited += 1

        for v in graph[u]:
            indegree[v] -= 1
            if indegree[v] == 0:
                queue.append(v)

    return visited == n

复杂度分析

• 时间复杂度：O(V + E)
• 空间复杂度：O(V)

易错点

• 判断“唯一”不是看能否完成拓扑排序，而是看每一步入度为 0 的顶点是否唯一。
• 更新邻接点入度时，所有出边都要处理。
• 若最后访问顶点数小于 n，说明图有环，也就不存在合法拓扑序。

对应题

未找到高度一致的公开原题。

难度

⭐️⭐️⭐️