207. Course Schedule

[namespace-io]

拓扑排序

本质上是判断一个图是否存在环，直接dfs会超时，使用一个数组保存dfs的结果，可以再优化
也可以使用BFS

class Solution {
public:
    bool dfs(int i, vector<bool>& visit,  vector<pair<int, int>>& p, vector<int>& f){
        if(f[i] != -1) return f[i] == 0 ? false : true;
        if(visit[i]) return false;
        
        visit[i] = true;
        bool b = true;
        for(int j = 0; j < p.size(); j++){
            auto pair = p[j];
            if(pair.first == i){
                b &= dfs(pair.second, visit, p, f);
            }
        }
        visit[i] = false;
        f[i] = b == true? 1 : 0;
        return b;
        
    }
    bool canFinish(int numCourses, vector<pair<int, int>>& prerequisites) {
        
            vector<bool> visit(numCourses, false);
            vector<int> f(numCourses, -1);
            for(int i = 0; i < numCourses; i++){

                if(dfs(i, visit, prerequisites, f) == false) return false;
            }

        return true;
    }
};