Course Schedule

#include <bits/stdc++.h>

using namespace std;

#define debug(x) cerr << #x << ": " << x << endl;
#define ll long long
#define ull unsigned long long
#define vi vector<int>


bool dfs_no_cycles(int node, vector<vi>& adj, vector<int>& states, list<int>& ordered) {
    states[node] = 1;

    // If successors
    for (int neighbor : adj[node]) {
        if (states[neighbor] == 0) {
            if (dfs_no_cycles(neighbor, adj, states, ordered) == false) return false;
        } else if (states[neighbor] == 1) {
            return false;
        }
    }

    // If no more successors to treat
    states[node] = 2;
    ordered.push_front(node);
    return true;
}

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

    vector<vi> successors (n+1);
    list<int> ordered;
    vector<int> states  (n+1, 0);
    int a,b;
    for (int i = 0; i < m; i++)
    {
        cin >> a >> b;
        successors[a].push_back(b);
    }
    
    for (int i = 1; i <= n; i++)
    {
        if (states[i] == 2) continue;
        if (dfs_no_cycles(i, successors, states, ordered) == false) {
            cout << "IMPOSSIBLE" << endl;
            return 0;
        }
    }




    // Print solution
    for (auto &&i : ordered)
    {   
        cout << i << ' ';
    }
    cout << endl;

    return 0;
}

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