Course Schedule

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

bool dfs(vector<vector<int>> & g, int node, vector<bool>& started, vector<bool>& finished, vector<int>& topSort){
    if (finished[node]){
        return true;
    }
    if (started[node]){
        return false;
    }

    started[node]=true;
    for (int next: g[node]){
        if (!dfs(g, next, started, finished, topSort)){
            return false;
        }
    }

    finished[node]=true;
    topSort.push_back(node);
    return true;
}

int main(){
    int n;
    int m;
    cin >> n >> m;

    vector<vector<int>> g(n+1,vector<int>(0));
    for (int i=0;i<m;i++){
        int from, to;
        cin >> from >> to;
        g[from].push_back(to);
    } 

    vector<bool> started(n+1, false);
    vector<bool> finished(n+1, false);
    vector<int> topSort(0);

    for (int i=1;i<=n;i++){
        if (!finished[i]){
            if (!dfs(g, i, started, finished, topSort)){
                cout << "IMPOSSIBLE\n";
                return 0;
            }
        }
    }

    reverse(topSort.begin(), topSort.end());
    for (const auto i: topSort){
        cout << i << ' ';
    }
    cout << '\n';
}

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED

Test 3

Verdict: ACCEPTED

Test 4

Verdict: ACCEPTED

Test 5

Verdict: ACCEPTED

Test 6

Verdict: ACCEPTED

Test 7

Verdict: ACCEPTED

Test 8

Verdict: ACCEPTED

Test 9

Verdict: ACCEPTED

Test 10

Verdict: ACCEPTED

Test 11

Verdict: ACCEPTED

Test 12

Verdict: ACCEPTED

Test 13

Verdict: ACCEPTED

Test 14

Verdict: ACCEPTED

Test 15

Verdict: ACCEPTED

Test 16

Verdict: ACCEPTED

Test 17

Verdict: ACCEPTED