Course Schedule (I & II)

有向图，尽量用BFS去做，明确，而且不stack overflow。(有向图，不选Union Find)

Course Schedule II

BFS, BFS的有向图建立indegree vector来做。无向图不行，无向图需要用set，来删除节点。

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

DFS:

DFS有向图，需要建立visited vector, int, 取0，-1，1. 其中 -1表示有loop。无向图，将前一个节点，作为pre带去dfs函数中，如果相等则continue。

class Solution {
public:
    vector<int> findOrder(int numCourses, vector<pair<int, int>>& prerequisites) {
        vector<int> ret;
        vector<vector<int>> graph(numCourses, vector<int>());
        for(auto it : prerequisites){
            graph[it.second].push_back(it.first);
        }
        vector<int> visited(numCourses, 0);
        for(int i=0; i<numCourses; i++){
            if(!dfs(graph, visited, ret, i)) return vector<int>();
        }
        if(ret.size() != numCourses) return vector<int>();
        reverse(ret.begin(), ret.end());
        return ret;
    }
    
    bool dfs(vector<vector<int>> &graph, vector<int> &visited, vector<int> &ret, int cur){
        if(visited[cur] == -1) return false;
        else if(visited[cur] == 1) return true;
        visited[cur] = -1;
        for(auto it : graph[cur]){
            if(!dfs(graph, visited, ret, it)) return false;
        }
        visited[cur] = 1;
        ret.push_back(cur);
        return true;
    }
};