LeetCode 210. 课程表 II（拓扑排序）

答案参考leetcode官方题解
比如：例子 4，[[1,0],[2,0],[3,1],[3,2]]
课程0没有要依赖的课程
课程1依赖课程0 1→0
课程2依赖课程0 2→0
课程3依赖课程1和2 3→1，2

每个课程都有三种状态：0还没被搜索到，1正在搜索中，2已经搜索完成，放在最终排序中

解题过程可以分解为：
1、把每个课程的依赖关系列出来
2、然后开始以此遍历没有搜索到的课程
3、没有搜索到课程，进行dfs搜索，状态变为1（正在搜索），找到该课程依赖的课程
4、dfs找到最边缘的课程（不需要依赖任何课程），放到最终排序中，已经完成搜索，状态变为2
要注意如果中间环（相互依赖）那么进行标记，最后返回空排序

代码如下：

class Solution {
public:
    vector<vector<int>>edgs;
    vector<int>res;
    vector<int>visit;
    bool valid=true;
    void dfs(int idx){
        visit[idx]=1;
        for(int i=0;i<edgs[idx].size();i++){
            if(visit[edgs[idx][i]]==0){
                dfs(edgs[idx][i]);
            }
            else if(visit[edgs[idx][i]]==1){
                valid=false;
            }
        }
        visit[idx]=2;
        res.push_back(idx);
    }
    vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) {
        edgs.resize(numCourses);
        visit.resize(numCourses);
        for(int i=0;i<prerequisites.size();i++){
            edgs[prerequisites[i][0]].push_back(prerequisites[i][1]);
        }
        for(int i=0;i<visit.size();i++){
            if(visit[i]==0){
                dfs(i);
            }
            if(valid==false) return {};
        }
        return res;
    }
};
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