课程表

解题思路

广度遍历的思路。
1.首先将给定的课程表关系图转换为图的邻接表。
2.深度遍历邻接表。使用visited来记录节点是否在搜索中被遍历过，如果被遍历过，那么说明有环，直接退出。
3.每次将遍历到的最后一个值，作为结果存放到结果栈中。

代码

cpp

class Solution {
public:
    vector<vector<int>> eds;
    vector<int> visited;
    vector<int> finished;
    bool invaild;

    void dfs(int i){
        if(visited[i]==2){
            return;
        }
        visited[i] = 1;
        for(const auto& s : eds[i]){
            if(visited[s]==1){
                invaild = true;
                return;
            }
            else if(visited[s]==0){
                dfs(s);              
                if(invaild){
                    return;
                }
            }
        }
        visited[i]=2;
        finished.push_back(i);
    }

    vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) {
        // if(prerequisites.size()==0 || prerequisites[0].size()==0){
        //     return prerequisites[0];
        // }
        eds.resize(numCourses);
        visited.resize(numCourses);
        //转换为邻接表
        for(const auto& info : prerequisites){
            eds[info[1]].push_back(info[0]);            
        }

        for(int i=0; i<numCourses; i++){
                dfs(i);
        }
        if(invaild){
            return {};
        }
        reverse(finished.begin(),finished.end());
        return finished;
;

    }
};