207

class Solution {
public:
    bool canFinish(int n, vector<vector<int>>& prerequisites) {
        // Create adj list and indegree vector.
        vector<vector<int>> graph(n);
        vector<int> inDegree(n, 0);
        for(auto pre: prerequisites){
            graph[pre[1]].push_back(pre[0]);
            inDegree[pre[0]]++;
        }

        // Topo sort using bfs.
        queue<int> q;
        for(int i=0; i<n; i++)
            if(!inDegree[i])
                q.push(i);

        while(!q.empty()){
            int node = q.front(); q.pop();
            for(auto child: graph[node])
                if(--inDegree[child] == 0)
                    q.push(child);
        }

        // Check for cycle.
        for(int i=0; i<n; i++)
            if(inDegree[i])
                return false;
        return true;
    }
};