Course Schedule

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

using Edges = vector<vector<int>>; 

struct TopoSort {
    enum class Status : uint8_t { to_visit, visiting, visited };

    const Edges& graph;
    const int n;
    vector<Status> status;
    vector<int> order;
    vector<int>::reverse_iterator it;

    TopoSort(const Edges& graph) :
        graph(graph),
        n(graph.size()),
        status(n, Status::to_visit),
        order(n),
        it(order.rbegin()) {}

    bool Sort() 
    {
        for (int i = 0; i < n; ++i) 
            if (status[i] == Status::to_visit && !Dfs(i)) 
                return false;
        return true;
    }

    bool Dfs(const int u) 
    {
        status[u] = Status::visiting;
        for (const int v : graph[u]) 
        {
            if (status[v] == Status::visiting) 
                return false;
            if (status[v] == Status::to_visit && !Dfs(v)) 
                return false;
        }
        status[u] = Status::visited;
        *it++ = u;
        return true;
    }
};

int main()
{
    int n, m;
    cin >> n >> m;
    Edges edge(n+1);
    for(int i=1; i<=m; i++)
    {
        int x, y;
        cin >> x >> y;
        edge[x].push_back(y);
    }
    TopoSort t(edge);
    if(t.Sort()) for(const int x : t.order) {
        if(x != 0)
            cout << x << " ";
    } else {
        cout << "IMPOSSIBLE";
    }
    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