2024·41 拓扑序唯一性判定：摘点摘出答案

本文属于「从暴力解到最优解」专题的第二组。这道题看着像要在多种拓扑排序算法里挑一个最优的，其实 Kahn 摘点算法本身就是唯一需要的工具——一边摘点一边数候选个数，直接判出唯一性。分不在算法选型，在三个判定分支和几个容易漏掉的细节。

题目

已知有向图 G 采用邻接矩阵存储，类型定义如下：

typedef struct {                    // 图的类型定义
    int  numVertices, numEdges;     // 图的顶点数和有向边数
    char VerticesList[MAXV];        // 顶点表，MAXV 为已定义常量
    int  Edge[MAXV][MAXV];          // 邻接矩阵
} MGraph;

请设计算法：int uniquely(MGraph G)，判定 G 是否存在唯一的拓扑序列，若是则返回 1，否则返回 0。要求：(1) 给出算法的基本设计思想（4 分）；(2) 采用 C 或 C++ 语言描述算法，关键之处给出注释（9 分）。总分 13 分。

题面同样没有出现「尽可能高效」——按总纲的分类，属于第二组。这道题的区分点在于把判定条件想全，算法本身并不需要多快。

直观解法：Kahn 摘点，每步数候选

拓扑排序最常见的实现是 Kahn 算法：反复找出当前入度为 0 的顶点摘掉，再把它指向的顶点入度减 1，直到摘完所有顶点。这道题不要求你输出某一条具体的拓扑序，只问「唯一不唯一」，而唯一性的判据恰好就藏在 Kahn 算法本身的执行过程里：每一步摘点时，如果零入度顶点不止一个，那么谁先谁后都合法，拓扑序就不唯一。

int uniquely(MGraph G) {
    int n = G.numVertices;
    int inDeg[MAXV] = {0};

    // ① 初始化入度数组：第 j 列上有多少非 0 项，inDeg[j] 就是多少
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            if (G.Edge[i][j] != 0) inDeg[j]++;

    // ② 共 n 步，每步必须恰好"摘掉一个"零入度顶点
    for (int step = 0; step < n; step++) {
        int zeroCount = 0, zeroIdx = -1;

        for (int i = 0; i < n; i++) {
            if (inDeg[i] == 0) {
                zeroCount++;
                zeroIdx = i;
            }
        }

        // 0 个 → 剩下的形成环；≥ 2 个 → 拓扑序不唯一；都返回 0
        if (zeroCount != 1) return 0;

        // 把 zeroIdx "摘掉"：置为 -1 避免下一轮误统计；其后继入度减 1
        inDeg[zeroIdx] = -1;
        for (int j = 0; j < n; j++)
            if (G.Edge[zeroIdx][j] != 0) inDeg[j]--;
    }

    return 1;
}

复杂度：初始化扫矩阵 $O (n^{2})$ ，主循环 n 步、每步统计和更新各 $O (n)$ ，合计仍是 $O (n^{2})$ ；空间只用一个入度数组， $O (n)$ 。

为什么它就是满分解

用总纲的「找浪费三问」审一遍：

有没有重复扫描？ 没有。每一步只扫一遍 inDeg 找候选，更新后继也只扫一遍该顶点这一行。
有没有重算已知的东西？ 没有。入度只在初始化时算一次，之后全靠增量维护（摘点时给后继的入度减 1），不会从头重新统计。
有没有放着性质不用？ 没有。DAG 拓扑序的唯一性本来就等价于「Kahn 每步候选数恒为 1」，这是判定这类问题的标准工具，用别的方法（比如枚举所有拓扑序再比对）反而是绕远路。

而且这道题给定的还是邻接矩阵，初始化入度这一步已经要扫完 $n^{2}$ 个元素，是存储方式本身带来的下界；主循环部分即便换成邻接表 + 队列实现的 Kahn 也是同一个量级。直观写法已经踩在下界上，没有再优化的空间。

真正的难点在这里

这道题真正的分数密度不在“会不会 Kahn 算法”，而在把整个判定逻辑的三个分支和几个实现细节全部想到、写对。

难点一：zeroCount 的三分支要说全。

zeroCount == 1：这一步没有选择，唯一确定下一个摘谁，继续往下走；
zeroCount >= 2：这一步至少有两个零入度顶点，它们之间一定没有边（否则其中一个入度就不会是 0），先摘谁都合法，所以拓扑序不唯一，直接返回 0；
zeroCount == 0（且还没摘完 n 个顶点）：说明剩下的顶点全部入度 ≥ 1，谁都摘不掉——这只可能是因为剩余部分含环，根本不是 DAG，没有拓扑序，同样返回 0。

很多同学只想到第一条和第二条，漏掉第三条「零个候选代表含环」，会把「压根不存在拓扑序」误判成某种特殊的「唯一」。代码里 if (zeroCount != 1) return 0; 这一行同时处理了 ≥2 和 ==0 两种情况，正是把两个不同原因的「不唯一/不存在」合并成同一个返回值 0，这一点在设计思想里也要讲清楚，不能只交代 ==1 的正常分支。

难点二：已摘顶点的入度必须置为 -1，不能留 0。 顶点被摘掉之后，如果 inDeg 还留着 0，下一轮统计 zeroCount 时会把这个已经处理过的顶点重复计入，要么把候选数错误地推高导致误判「不唯一」，要么造成同一个顶点被反复摘、逻辑死循环。inDeg[zeroIdx] = -1（或任意负值）就是把它从「候选池」里永久排除的标记，是本题最容易漏掉、也是漏了之后后果最严重的一处。

难点三：用固定 n 步循环，不要用 while 改写。 如果把外层循环改成「while 还有零入度顶点就继续摘」，会丢失一个关键信息：循环退出时，究竟是「n 个顶点全部摘完、成功结束」，还是「摘到一半 zeroCount 变成 0 提前卡住」？这两种情况必须区分对待，前者返回 1、后者返回 0。用 for (step = 0; step < n; step++) 搭配循环体内 zeroCount != 1 就提前 return 0，天然规避了这个歧义——如果 n 步都顺利跑完（每步都是 zeroCount == 1），循环正常结束后统一 return 1，逻辑干净利落。

摘点判唯一，看一遍

用一个 4 顶点的链式 DAG（0→1→2→3，拓扑序唯一，每一步零入度顶点都恰好 1 个）演示摘点过程：入度初始化、逐步摘点、入度置 -1、更新后继，最终返回 1。

加载可视化中...

演示为 JavaScript 版本，逻辑与上文 C 代码一一对应。（换一张两个顶点同时零入度的图，同样的代码会在第一步就返回 0。）

别画蛇添足

别用 DFS 三色标记判环来解这道题。 DFS 三色法（白/灰/黑）能判断图里有没有环、能不能生成拓扑序，但它天然按照访问顺序走出一条具体的路径，判断不出「这一步除了当前访问的顶点还有没有别的候选」——也就是回答不了「唯一不唯一」这个问题。这道题的核心诉求就是唯一性判定，DFS 判环解决的是另一个问题，用错了方向。
别用 while 循环漏判 processed == n。 前面已经说过原因：while 版本如果不额外记一个「已处理顶点数」并在循环外检查它是否等于 n，就没法区分「顺利摘完」和「摘到一半卡住」这两种截然不同的结局。想用 while 写也可以，但一定要把这个计数补上，否则等于把「zeroCount == 0 代表含环」这个分支悄悄弄丢了。

下一步

在 OJ 上验证你的写法：ds-2024-41 拓扑序唯一性判定
回到题库看这道题的完整解析与错因：真题库 · 数据结构

2024·41 拓扑序唯一性判定：摘点摘出答案 ​

题目 ​

直观解法：Kahn 摘点，每步数候选 ​

为什么它就是满分解 ​

真正的难点在这里 ​

摘点判唯一，看一遍 ​

别画蛇添足 ​

下一步 ​