题目

2023 年 10 月 26 日，神舟十七号载人飞船发射取得圆满成功，再次彰显了中国航天事业的辉煌成就。载人航天工程是包含众多子工程的复杂系统工程，为了保证工程的有序开展，需要明确各子工程的前导工程，以协调各子工程的实施。该问题可以简化、抽象为有向图的拓扑序列问题。

已知有向图 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 分）

解析

(1) 设计思想 [4 分]

核心结论：DAG 的拓扑序唯一 ⟺ Kahn 算法（不断"摘掉零入度顶点"）每一步都恰好只有 1 个零入度顶点。

为什么这个判定是对的？

• 某步出现 ≥ 2 个零入度顶点 ⇒ 拓扑序不唯一。设这一步同时有顶点 a、b 入度为 0，那么它们彼此之间一定没有边（否则其中一个入度 ≥ 1），所以"先 a 后 b" 和 "先 b 后 a" 都是合法的拓扑序，至少存在两种。
• 某步出现 0 个零入度顶点（且还没排完所有顶点）⇒ 剩下的顶点中存在环。环上的顶点入度恒 ≥ 1，永远摘不掉。这种情况下 G 根本不是 DAG，没有拓扑序，按题意也返回 0。
• 每一步都恰好 1 个零入度顶点 ⇒ 拓扑序唯一。每步没有"选择"，n 个位置依次被 n 个顶点唯一占据。

实现思路：

1. 先扫一遍邻接矩阵，算出每个顶点的入度，存入 inDeg[]；
2. 重复 n 次摘点：
   • 扫 inDeg[]，统计入度为 0 的顶点个数 zeroCount 与其中一个的下标；
   • zeroCount ≠ 1 直接返回 0；
   • 否则把这个顶点标记为"已摘"（入度置为 -1，避免下一轮再被统计），并把它所有后继的入度减 1；
3. n 步顺利做完，返回 1。

编者注（生僻术语）：题中"唯一拓扑序"在算法竞赛里常称为 Hamiltonian 路径——拓扑序唯一 ⟺ DAG 中存在一条经过所有顶点的有向路径。考研只需会"每步零入度顶点数 = 1"这个判定即可，不必深究。

(2) 代码实现 [9 分]

#define MAXV 100

typedef struct {
    int  numVertices, numEdges;
    char VerticesList[MAXV];
    int  Edge[MAXV][MAXV];
} MGraph;

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;

        // 扫一遍当前 inDeg，统计零入度顶点个数与下标
        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;
}

关键点说明：

• 必须把"已摘"的顶点入度置为 −1（或其他负值），不能仍留 0。否则下一轮扫描时它仍然是"入度为 0 的顶点"，会被反复计入 zeroCount，要么死循环要么误判为非唯一。这是本题最常见的细节失分点。
• 不要省去外层 n 次循环：很多同学想用 while 循环"直到没有零入度顶点为止"，但这样无法区分"刚好走到第 n 步成功结束"和"中途因 zeroCount=0 卡住"。用固定 n 次循环 + 提前返回最稳。
• 本题为什么不用队列？ Kahn 算法的标准实现是用队列存零入度顶点。但本题需要判断"每一步是不是恰好 1 个候选"，用队列也能写（每次出队前检查队列大小是否为 1），但要确保队列里的元素都是当前轮次新产生的零入度顶点；用直接扫 inDeg 的写法更直白、不易错。
• 复杂度：时间 O(n²)。初始化扫邻接矩阵 O(n²)；外循环 n 次，每次扫 inDeg O(n) + 更新后继 O(n)，共 O(n²)。两部分相加仍是 O(n²)。空间 O(n)，仅 inDeg 数组。
• 正确性补充：连环的情况。若 G 含环，则环上顶点永远摘不掉。当摘点摘到非环部分耗尽时，剩下的顶点 inDeg 全 ≥ 1，下一步 zeroCount = 0 → 提前返回 0。所以本算法天然兼容"判 DAG"，无需另写判环逻辑。