Description

Submission

class Solution {
    vector<int> visited;
    vector<vector<int>> next;
    
    bool dfs(int cur)
    {
        if (visited[cur]==1) return true;

        visited[cur] = 2;
        for (int next: next[cur])
        {
            if (visited[next]==1) continue;
            if (visited[next]==2) return false;
            if (dfs(next)==false)  return false;
        }
        visited[cur] = 1;
        return true;
    }
public:
    bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
        visited.resize(numCourses);
        next.resize(numCourses);

        for(auto p : prerequisites) {
            next[p[0]].push_back(p[1]);
        }

        for(int i = 0; i < numCourses; ++i) {
            if(dfs(i) == false) return false;
        }
        return true;
    }
};

class Solution {
public:
    bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
        vector<vector<int>> next(numCourses);
        vector<int> inDegree(numCourses, 0);

        for(auto& p: prerequisites) {
            next[p[0]].push_back(p[1]);
            ++inDegree[p[1]];
        }
        
        queue<int> q;
        int count = 0;
        for(int i = 0; i < numCourses; ++i) {
            if(!inDegree[i]) {
                q.push(i);
                ++count;
            }
        }

        while(!q.empty()) {
            int cur = q.front();
            q.pop();

            for(auto x: next[cur]) {
                --inDegree[x];
                if(!inDegree[x]) {
                    q.push(x);
                    ++count;
                }
            }
        }

        return count == numCourses;
    }
};