topsort.cpp

#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
#include <stack>
#define WHITE 0
#define GRAY 1
#define BLACK 2
using namespace std;

class Graph {
public:
    int n;
    vector<int> *adj;

    Graph(int n){
        this->n = n;
        adj = new vector<int>[n];
    }

    void add(int a, int b) {
        adj[a].push_back(b);
    }

    void topsort(int v, int color[], stack<int> &s, bool &cyclic){
        if (cyclic)
            return;
        color[v] = GRAY;
        vector<int>::iterator it;
        for (it = adj[v].begin(); it != adj[v].end(); ++it){
            if (color[*it] == GRAY){
                cyclic = true;
                return;
            }
            if (color[*it] == WHITE)
                topsort(*it, color, s, cyclic);
        }
        color[v] = BLACK;
        s.push(v);
    }

    void topsort() {
        stack<int> s;
        bool cyclic = false;
        int *color = new int[n];
        for (int i = 0; i < n; i++)
            color[i] = WHITE;

        for (int i = 0; i < n; i++)
            if (color[i] == WHITE)
                topsort(i, color, s, cyclic);
        if (cyclic)
            cout << "-1";
        else
            while (s.size() > 1) {
                cout << s.top() << ' ';
                s.pop();
            }
    }
};

int main() {
    int n, m, a, b;
    cin >> n >> m;
    Graph d(n+1);
    while(m-- && cin >> a >> b){
        d.add(a, b);
    }
    d.topsort();
    return 0;
}