Cod sursa(job #1176266)

Utilizator usakoTsu Usako usako Data 25 aprilie 2014 20:15:20
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.72 kb
#include <cstdio>
#include <vector>
#include <bitset>
#include <stack>
#define NM 50000
using namespace std;

stack<int> st;
bitset<NM> viz;
vector<int> a[NM];
int N,M;

void dfs(int nod) {
  viz[nod] = 1;
  vector<int>::iterator it = a[nod].begin();
  for (; it != a[nod].end(); ++it) {
    if (viz[*it]) {
      continue;
    }
    dfs(*it);
  }
  st.push(nod);
}
int main() {
  freopen("sortaret.in","r",stdin);
  freopen("sortaret.out","w",stdout);
  scanf("%d %d", &N, &M);
  int x,y;
  while (M--) {
    scanf("%d %d", &x, &y);
    a[x-1].push_back(y-1);
  }
  for (int i = 0; i < N; ++i) {
    if (viz[i]) {
      continue;
    }
    dfs(i);
  }
  while (!st.empty()) {
    printf("%d ", st.top() +1);
    st.pop();
  }
  return 0;
}