Course Schedule

There are a total of n tasks you have to pick, labeled from 0 to n-1. Some tasks may have prerequisites tasks, for example to pick task 0 you have to first finish tasks 1, which is expressed as a pair: [0, 1]

Given the total number of n tasks and a list of prerequisite pairs of size m. Find a ordering of tasks you should pick to finish all tasks.

Note: There may be multiple correct orders, you just need to return one of them. If it is impossible to finish all tasks, return an empty array. Returning any correct order will give the output as 1, whereas any invalid order will give the output 0.

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

class Solution {
public:
    vector<int> findOrder(int n, int m, vector<vector<int>> prerequisites) {
        vector<int> res, ind(n);
        vector<vector<int>> adj(n);
        for(auto& q : prerequisites) {
            int u = q[1], v = q[0];
            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()) {
            int u = q.front(); q.pop();
            res.push_back(u);
            for(auto& v : adj[u]) {
                if(--ind[v] == 0) q.push(v);
            }
        }
        
        return res.size() == n ? res : vector<int>() = {};
    }
};