Course Schedule

#include <bits/stdc++.h>
using namespace std;

const int N = 1e5+1;

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

    vector<vector<int>> dep(n+1);
    uint8_t vis[N] = {};
    int ans[N] = {};

    for(int i=0; i<m; i++) {
        int a, b;
        cin >> a >> b;
        dep[a].push_back(b);
    }

    stack<int> q;
    int l = n;

    for(int i=1; i <= n; i++) {
        if (vis[i]) continue;
        q.push(i);

        while(q.size()) {
            auto node = q.top();

            if(vis[node] == 2) {
                q.pop();
                continue;
            };

            if (vis[node] == 1) {
                vis[node] = 2;
                ans[l--] = node;
            } else {
                vis[node] = 1;
                for(const auto& b : dep[node]) {
                    if(vis[b] == 1) {
                        cout << "IMPOSSIBLE\n";
                        return 0;
                    }
                    else
                        q.push(b);
                }
            }
        }
    }

    for(int i=1; i <= n; i++) {
        cout << ans[i] << ' ';
    }

    cout << '\n';


    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