210

class Solution {
public:
    vector<int> findOrder(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.
        vector<int> order;
        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();
            order.push_back(node);
            for(auto child: graph[node])
                if(--inDegree[child] == 0)
                    q.push(child);
        }

        // Check for cycle.
        if(order.size() != n) return vector<int>{};
        return order;
    }
};