[LeetCode] 210. Course Schedule II

grandyang commented 5 years ago

There are a total of n courses you have to take, labeled from 0 to n-1.

Some courses may have prerequisites, for example to take course 0 you have to first take course 1, which is expressed as a pair: [0,1]

Given the total number of courses and a list of prerequisite pairs, return the ordering of courses you should take to finish all courses.

There may be multiple correct orders, you just need to return one of them. If it is impossible to finish all courses, return an empty array.

Example 1:

Input: 2, [[1,0]] 
Output: [0,1]
Explanation: There are a total of 2 courses to take. To take course 1 you should have finished   
             course 0. So the correct course order is [0,1] .

Example 2:

Input: 4, [[1,0],[2,0],[3,1],[3,2]]
Output: [0,1,2,3] or [0,2,1,3]
Explanation: There are a total of 4 courses to take. To take course 3 you should have finished both     
             courses 1 and 2. Both courses 1 and 2 should be taken after you finished course 0. 
             So one correct course order is [0,1,2,3]. Another correct ordering is [0,2,1,3] .

Note:

The input prerequisites is a graph represented by a list of edges, not adjacency matrices. Read more about how a graph is represented.
You may assume that there are no duplicate edges in the input prerequisites.

Hints:

This problem is equivalent to finding the topological order in a directed graph. If a cycle exists, no topological ordering exists and therefore it will be impossible to take all courses.
Topological Sort via DFS - A great video tutorial (21 minutes) on Coursera explaining the basic concepts of Topological Sort.
Topological sort could also be done via BFS.

这题是之前那道 Course Schedule 的扩展，那道题只让我们判断是否能完成所有课程，即检测有向图中是否有环，而这道题我们得找出要上的课程的顺序，即有向图的拓扑排序 Topological Sort，这样一来，难度就增加了，但是由于我们有之前那道的基础，而此题正是基于之前解法的基础上稍加修改，我们从 queue 中每取出一个数组就将其存在结果中，最终若有向图中有环，则结果中元素的个数不等于总课程数，那我们将结果清空即可。代码如下：

class Solution {
public:
    vector<int> findOrder(int numCourses, vector<pair<int, int>>& prerequisites) {
        vector<int> res;
        vector<vector<int> > graph(numCourses, vector<int>(0));
        vector<int> in(numCourses, 0);
        for (auto &a : prerequisites) {
            graph[a.second].push_back(a.first);
            ++in[a.first];
        }
        queue<int> q;
        for (int i = 0; i < numCourses; ++i) {
            if (in[i] == 0) q.push(i);
        }
        while (!q.empty()) {
            int t = q.front();
            res.push_back(t);
            q.pop();
            for (auto &a : graph[t]) {
                --in[a];
                if (in[a] == 0) q.push(a);
            }
        }
        if (res.size() != numCourses) res.clear();
        return res;
    }
};

Github 同步地址：

https://github.com/grandyang/leetcode/issues/210

类似题目：

Sequence Reconstruction

参考资料：

https://leetcode.com/problems/course-schedule-ii/

https://leetcode.com/problems/course-schedule-ii/discuss/59330/Concise-JAVA-solution-based-on-BFS-with-comments

https://leetcode.com/problems/course-schedule-ii/discuss/59342/Java-DFS-double-cache-visiting-each-vertex-once-433ms

LeetCode All in One 题目讲解汇总(持续更新中...)

swhaleDCC commented 5 years ago

您好，我把您的代码复制到力扣显示编译错误，改了一下第一个for后才通过 for (auto a : prerequisites) { graph[a[1]].push_back(a[0]); //有向图从a[1]指向a[0] ++in[a[0]]; //一维数组 in 来表示每个顶点的入度 } 请问这是什么原因？

szh-maker commented 3 years ago

您好，我把您的代码复制到力扣显示编译错误，改了一下第一个for后才通过 for (auto a : prerequisites) { graph[a[1]].push_back(a[0]); //有向图从a[1]指向a[0] ++in[a[0]]; //一维数组 in 来表示每个顶点的入度 } 请问这是什么原因？因为博主的是一维向量中的参数是pair

grandyang / leetcode

[LeetCode] 210. Course Schedule II #210