Cinte's Leetcode Record
0%

210. 课程表 II

Posted on Edited on In Disqus:
Symbols count in article: 1.2k Reading time ≈ 1 mins.

210. 课程表 II

参考(´∇｀) 被你发现啦~207. Course Schedule | Cinte's Leetcode Record

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
class Solution {
public:
    vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) {
        vector<vector<int>> graph(numCourses);
        for(auto& prerequisite : prerequisites)
            // 注意这里的方向不能换，因为这种写法是往前找先决课程
            // 如果找到末尾的话说明找到了一个最基层的先决课程，需要最先学
            // 如果方向换的话就是从底层网上走，找到一个可以完成学习的课程，是最后的那一个课程
            // 为了结果返回的正确性，不能改变方向，反之207题中只是为了判断环路，所以可以返回方向。
            graph[prerequisite[0]].push_back(prerequisite[1]);
        vector<int> checked(numCourses, 0);
        vector<int> visited(numCourses, 0);
        vector<int> ret;
        ret.reserve(numCourses);
        for(int i = 0; i < numCourses; ++i)
            if(!dfs(ret, i, checked, visited, graph))
                return {};
        return ret;
    }
private:
    bool dfs(vector<int>& ret, int course, vector<int>& checked, vector<int>& visited, vector<vector<int>>& graph)
    {
        if(visited[course])
            return false;
        if(checked[course])
            return true;
        visited[course] = 1;
        for(auto& p : graph[course])
            if(!dfs(ret, p, checked, visited, graph))
                return false;
        checked[course] = 1;
        // 找到了一个没有被访问过的基层，加入返回列表中
        ret.push_back(course);
        visited[course] = 0;
        return true;
    }
};