2024年408算法大题

题目描述与分析

给出一个以邻接矩阵表示的有向图，实现一个判断其拓扑排序是否唯一的函数

拓扑排序首次考代码大题。在 408 算法大题中，由于不可以使用 STL，因此要用一个容量很大的数列去模拟队列。但是思考本题后发现，如果一个图的拓扑排序是唯一的，那么它的辅助队列的任何时刻，容量都不超过 1，否则在下一轮输出时可以任选队列中的一个输出，从而造成拓扑排序不唯一。基于这个原理，且考虑到图的节点编号非负，那么可以用一个 int 型变量模拟队列，其值为 -1 表示队列为空，否则其值就是队列中的唯一元素。该方法实现了最优空间复杂度，避免了用数组模拟队列的麻烦。类似的优化思路还有，如果语言中没有 Pair 类似的实现，但是想使用一个 int 类型的二元组，可考虑用一个 long 变量进行模拟，高 32 位和低 32 位存储两个 int，取出和放入时使用相应的掩码 AND 运算即可

特别注意的是，根据题意，如果图中不存在拓扑排序，我们也应返回 -1

答案

int unique(vector<vector<int>> &graph) {
    int queue = -1; // 本题的性质决定合法的队列大小为1，因此用一个int模拟就够了
    int num = 0; // 统计以构建拓扑排序的节点数
    int n = graph.size();
    int inDegree[n];
    for (int i = 0; i < n; i++) {
        inDegree[i] = 0;
    }
    // 首次遍历邻接矩阵，统计每个节点的入度
    for (int i = 0; i < n; i++) {
        int degree = 0;
        for (int j = 0; j < n; j++) {
            if (graph[j][i] != 0) {
                degree++;
            }
        } 
        // 入队入度为1的节点
        if (degree == 0) {
            if (queue != -1) {
                return -1; // 不存在唯一拓扑排序
            }
            queue = i; // 模拟入队
        }
    }
    // 构建拓扑排序
    while (queue != -1) {
        // 模拟出队
        int cur = queue;
        num++;
        queue = -1; // queue要置-1.否则死循环
        // 遍历以cur作为弧尾的边，将弧头的入度-1
        for (int i = 0; i < n; i++) {
            if (graph[cur][i] != 0) {
                graph[cur][i] = 0;
                inDegree[i]--;
                if (inDegree[i] == 0) {
                    if (queue != -1) {
                        return -1;
                    }
                    queue = i;
                }
            }
        }
    }
    // 若最终未能构建拓扑排序，也返回-1
    if (num != n) {
        return -1;
    }
    return 1; // ok
}