Prerequisite Tasks

There are a total of N tasks, labeled from 0 to N-1. Some tasks may have prerequisites, for example to do task 0 you have to first complete task 1, which is expressed as a pair: [0, 1]
Given the total number of tasks N and a list of prerequisite pairs P, find if it is possible to finish all tasks.

• Time : O(v + e)
• Space : O(v + e)

c++

class Solution {
public:
    bool isPossible(int N, vector<pair<int, int>>& A) {
        vector<int> ind(N);
        vector<vector<int>> adj(N);
        
        for(auto& p : A) {
            int u = p.first, v = p.second;
            adj[u].push_back(v);
            ind[v]++;
        }
        
        queue<int> q;
        for(int i = 0; i < N; i++)
            if(ind[i] == 0) q.push(i);
            
        while(!q.empty()) {
            auto u = q.front(); q.pop();
            for(auto& v : adj[u]) {
                if(--ind[v] == 0)
                    q.push(v);
            }
        }

        return accumulate(begin(ind), end(ind), 0) == 0;
    }
};