Cod sursa(job #1540325)

Utilizator pickleVictor Andrei pickle Data 2 decembrie 2015 17:24:33
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.73 kb
#include <iostream>
#include <fstream>
#include <string>
#include <vector>

#define  REP(i, n)  for (int i=0; i<int(n); ++i)
#define  FOR(i, n)  for (int i=1; i<=int(n); ++i)

using namespace std;
typedef vector<int> vi;

const int Nmax = 50333;

vi G[Nmax];
int vis[Nmax], ret[Nmax];

void dfs(int vertex) {
  if (vis[vertex])
    return;
  for(auto nbr: G[vertex]) {
    dfs(nbr);
  }
  vis[vertex] = 1;
  ret[++ret[0]] = vertex;
}

int main() {
  ifstream fin ("sortaret.in");
  ofstream fout ("sortaret.out");

  int N, M, a, b;
  fin >> N >> M;
  while(M--) {
    fin >> a >> b;
    G[a].push_back(b);
  }

  FOR(i, N) {
    dfs(i);
  }

  for (int i = ret[0]; i > 0; i--) {
    fout << ret[i] << (i == 1 ? '\n' : ' ');
  }

  return 0;
}