LeetCode 210. 课程表 II

题目描述

现在你总共有 n 门课需要选，记为 0 到 n-1。

在选修某些课程之前需要一些先修课程。 例如，想要学习课程 0 ，你需要先完成课程 1 ，我们用一个匹配来表示他们: [0,1]

给定课程总量以及它们的先决条件，返回你为了学完所有课程所安排的学习顺序。

可能会有多个正确的顺序，你只要返回一种就可以了。如果不可能完成所有课程，返回一个空数组。

示例 1:

输入: 2, [[1,0]] 
输出: [0,1]
解释: 总共有 2 门课程。要学习课程 1，你需要先完成课程 0。因此，正确的课程顺序为 [0,1] 。

示例 2:

输入: 4, [[1,0],[2,0],[3,1],[3,2]]
输出: [0,1,2,3] or [0,2,1,3]
解释: 总共有 4 门课程。要学习课程 3，你应该先完成课程 1 和课程 2。并且课程 1 和课程 2 都应该排在课程 0 之后。
     因此，一个正确的课程顺序是 [0,1,2,3] 。另一个正确的排序是 [0,2,1,3] 。

说明:

1. 输入的先决条件是由边缘列表表示的图形，而不是邻接矩阵。详情请参见图的表示法。
2. 你可以假定输入的先决条件中没有重复的边。

提示:

1. 这个问题相当于查找一个循环是否存在于有向图中。如果存在循环，则不存在拓扑排序，因此不可能选取所有课程进行学习。
2. 通过 DFS 进行拓扑排序 - 一个关于Coursera的精彩视频教程（21分钟），介绍拓扑排序的基本概念。
3. 拓扑排序也可以通过 BFS 完成。

题解

如提示，目的是判断有向图是否无环，常用的判断方法使用拓扑排序。

卡恩算法

算法

• 创建有向表 graph，L 是存放结果的列表。
• 找到入度为 0 的节点，放入 L 中，因为这些节点没有任何父节点，也就是不需要先修课程。
• 将与这些节点相连的边从图中去掉，再寻找入度为 0 的节点。
• 重复上述操作，直到找不到入度为 0 的节点。
• 如果 L 的元素个数和节点总数相同，说明排序完成。
• 如果 L 的元素个数和节点总数不同，说明原图中存在环，无法进行拓扑排序。

代码

• C++
• JavaScript

C++

//
vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) {
    if (!numCourses) {
        return {};
    }
    vector<int> ans;
    vector<vector<int>> graph(numCourses, vector<int>());
    vector<int> incoming(numCourses, 0);
    for (auto& p : prerequisites) {
        ++incoming[p[0]];
        graph[p[1]].push_back(p[0]);
    }
    for (int i = 0; i < numCourses; ++i) {
        if (incoming[i] == 0) {
            ans.push_back(i);
        }
    }
    for (int i = 0; i < ans.size(); ++i) {
        int from = ans[i];
        for (int &to : graph[from]) {
            --incoming[to];
            if (incoming[to] == 0) {
                ans.push_back(to);
            }
        }
    }
    return ans.size() == numCourses ? ans : vector<int>();
}

JavaScript

/**
 * @param {number} numCourses
 * @param {number[][]} prerequisites
 * @return {boolean}
 */
var findOrder = function(numCourses, prerequisites) {
    const incoming = new Array(numCourses).fill(0);
    const graph = new Array(numCourses).fill(0).map(()=>new Set());
    for(const [to, from] of prerequisites) {
        incoming[to]++;
        graph[from].add(to);
    }
    const L = [];
    const queue = [];
    for(let i = 0; i < numCourses; i++) {
        if(incoming[i] === 0) {
            queue.push(i);
        }
    }
    while(queue.length) {
        const from = queue.shift();
        L.push(from);
        for(const to of graph[from]) {
            incoming[to]--;
            if(incoming[to] === 0) {
                queue.push(to);
            }
        }
    }
    return L.length === numCourses ? L : [];
};

复杂度

• 时间复杂度：$O(N)$，$N$ 为节点总数，因为每个节点只会被处理一次。
• 空间复杂度：$O(N)$，需要维护一个队列。

深度优先搜索

算法

• 创建有向表 graph，ans 是存放结果的列表。
• 依次遍历所有节点，例如从节点 A 出发。
• 将 A 标记为访问中 visiting，递归判断 A 的后续节点。
• 如果出现标记为访问中 visiting 的节点，说明出现环，无法进行拓扑排序。
• 如果节点没有后续节点，说明从 A 出发没有出现环。
• 将 A 放入 ans 的头部。

代码

• C++
• JavaScript

C++

//
vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) {
    vector<int> ans;
    vector<vector<int>> graph(numCourses, vector<int>());
    for (auto &p : prerequisites) {
        graph[p[1]].push_back(p[0]);
    }
    vector<bool> visiting(numCourses, false);
    vector<bool> visited(numCourses, false);
    for (int c = 0; c < numCourses; ++c) {
        if (!dfs(c, graph, visiting, visited, ans)) {
            return {};
        }
    }
    return ans;
}
bool dfs(int course, vector<vector<int>> &graph, vector<bool> &visiting, vector<bool> &visited, vector<int> &ans) {
    if (visiting[course]) {
        return false;
    }
    if (visited[course]) {
        return true;
    }
    visiting[course] = true;
    for (int &to : graph[course]) {
        if (!dfs(to, graph, visiting, visited, ans)) {
            return false;
        }
    }
    visiting[course] = false;
    visited[course] = true;
    ans.insert(ans.begin(), course);
    return true;
}

JavaScript

/**
 * @param {number} numCourses
 * @param {number[][]} prerequisites
 * @return {boolean}
 */
var findOrder = function(numCourses, prerequisites) {
    const graph = new Array(numCourses).fill(0).map(()=>new Set());
    for(const [to, from] of prerequisites) {
        graph[from].add(to);
    }
    const ans = [];
    const visiting = new Array(numCourses).fill(false);
    const visited = new Array(numCourses).fill(false);
    const dfs = c => {
        if(visiting[c]) {
            return false;
        }
        if(visited[c]) {
            return true;
        }
        visiting[c] = true;
        for(const to of graph[c]) {
            if(!dfs(to)) {
                return false;
            }
        }
        visiting[c] = false;
        visited[c] = true;
        ans.unshift(c);
        return true;
    };
    for(let c = 0; c < numCourses; c++) {
        if(!dfs(c)) {
            return [];
        }
    }
    return ans;
};

复杂度

• 时间复杂度：$O(N)$。
• 空间复杂度：$O(N)$。

参考链接

• 210. Course Schedule II, LeetCode Solution.
• Topological sorting, Wikipeedia.