Leetcode 210. Course Schedule II [Medium]

Problem:

source: Course Schedule II

Identify problem

Similar to leetcode207 Course Schedule but this time we have to return ordered result as an output.

Approach

We are going to use topological sort, and more about this topological sort could be viewed on my topological sort post.

Code

class Solution {
public:
    vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) {
        
        unordered_map<int, vector<int>> graph;
        
        for(auto& i : prerequisites)
        {
            graph[i[1]].push_back(i[0]);
        }
        
        vector<int> in_degree(numCourses);
        for(int i=0; i<numCourses; ++i)
        {
            for(auto& to: graph[i])
            {
                in_degree[to] = in_degree[to] + 1; 
            }
        }
        
        queue<int> q;
        for(int i=0; i<numCourses; ++i)
        {
            if(in_degree[i] == 0)
            {
                q.push(i);
            }
        }
        
        
        int index = 0;
        vector<int> order(numCourses);
        while(!q.empty())
        {
            int at = q.front(); q.pop();
            order[index++] = at;
            for(auto to: graph[at])
            {
                in_degree[to] = in_degree[to] - 1;
                if(in_degree[to] == 0)
                {
                    q.push(to);
                }
            }
        }
        
        if(index != numCourses)
        {
            return {};
        }
        return order;
        
    }
};