Course Schedule

You have to complete n courses. There are m requirements of the form "course a has to be completed before course b". Your task is to find an order in which you can complete the courses.

Example:

Input:  n = 5, m = 3, edges = {{1, 2}, {3, 1}, {4, 5}}
Output: 3 4 1 5 2 

Approach

C++

#include <bits/stdc++.h>
using namespace std;
vector<int> arr[1000001];
int in[1000001];
vector<int> path;
bool kahn(int n)
{
    queue<int> q;
    for (int i = 1; i <= n; i++)
    {
        if (in[i] == 0)
            q.push(i);
    }
    while (!q.empty())
    {
        int curr = q.front();
        q.pop();
        path.push_back(curr);
        for (int child : arr[curr])
        {
            in[child]--;
            if (in[child] == 0)
                q.push(child);
        }
    }
    if (path.size() == n)
        return true;
    return false;
}
int main()
{
    int n = 5, m = 3;
    vector<vector<int>> edges = {{1, 2}, {3, 1}, {4, 5}};
    for (int i = 0; i < m; i++)
    {
        int a = edges[i][0], b = edges[i][1];

        arr[a].push_back(b);
        in[b]++;
    }
    if (kahn(n))
    {
        for (int i = 0; i < path.size(); i++)
            cout << path[i] << " ";
        cout << "\n";
    }
    else
        cout << "IMPOSSIBLE\n";

    return 0;
}