Cod sursa(job #1492082)

Utilizator ELHoriaHoria Cretescu ELHoria Data 27 septembrie 2015 02:07:51
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.75 kb
#include <fstream>
#include <vector>
#include <algorithm>


using namespace std;

void dfs(int v, vector< vector<int> >& graph, vector<int>& ret,
    vector<bool>& used) {
  used[v] = 1;
  for (auto& w : graph[v]) {
    if (!used[w])
      dfs(w, graph, ret, used);
  }
  ret.push_back(v);
}

int main() {
  ifstream cin("sortaret.in");
  ofstream cout("sortaret.out");
  int n, m, x, y;
  cin >> n >> m;
  vector< vector<int> > graph(n);
  vector<int> ret, in(n);
  vector<bool> used(n);
  while (m--) {
    cin >> x >> y;
    graph[--x].push_back(--y);
    in[y]++;
  }
  for (int i = 0; i < n; i++) {
    if (!in[i] && !used[i]) {
      dfs(i, graph, ret, used);
    }
  }
  reverse(begin(ret), end(ret));
  for (auto& x : ret) {
    cout << x + 1 << " ";
  }
}