Skip to content

Instantly share code, notes, and snippets.

@keon

keon/topsort.cpp

Created Feb 23, 2017
Embed
What would you like to do?
#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;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment