class Solution {
public:
    bool isCycle(vector<vector<int>>& graph, vector<int>& visited, int current) {
        if(visited[current] == 1) return true;
        if(visited[current] == 2) return false;

        visited[current] = 1;
        for(int& edge : graph[current]) {
            if(isCycle(graph, visited, edge) == true) return true;
        }        

        visited[current] = 2;
        return false;
    }

    bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
        vector<vector<int>> graph(numCourses, vector<int>(0));

        // Establish graph
        for(auto pre : prerequisites) {
            graph[pre[1]].push_back(pre[0]);
        }

        // 0: unvisited
        // 1: visiting
        // 2: visited
        vector<int> visited(numCourses, 0);

        for(int i = 0; i < numCourses; i++) {
            if(isCycle(graph, visited, i) == true) return false;
        }

        return true;
    }
};

class Solution {
public:
    bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
        vector<vector<int>> graph(numCourses);
        vector<int> indegree(numCourses);
        queue<int> que;

        for(auto& pre : prerequisites) {
            graph[pre[1]].push_back(pre[0]);
            indegree[pre[0]]++;
        }

        for(int i = 0; i < numCourses; i++) {
            // put indegree = 0 node into queue
            if(indegree[i] == 0) que.push(i);
        }

        if(que.empty() == true) return false;

        int nodeVisited = 0;

        while(que.empty() == false) {
            int current = que.front();
            que.pop();
            nodeVisited++;
            // iterate all neighbors
            for(auto& neighbor : graph[current]) {
                indegree[neighbor]--;
                // put neighbor if indegree decreases to zero
                if(indegree[neighbor] == 0) que.push(neighbor);
            }
        }

        // if not all visited, return false
        return nodeVisited == numCourses;
    }
};