Cod sursa(job #1686232)

Utilizator BrandonChris Luntraru Brandon Data 12 aprilie 2016 09:50:56
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.82 kb
#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;

const int MaxN = 50005;

ifstream cin("sortaret.in");
ofstream cout("sortaret.out");

vector <int> G[MaxN], toposort;

int EnDeg[MaxN];
bool used[MaxN];
int n, m;

void Dfs(int node) {
  used[node] = true;

  for(auto nxt: G[node]) {
    if(used[nxt]) {
      continue;
    }

    Dfs(nxt);
    toposort.push_back(nxt);
  }
}

int main() {
  cin >> n >> m;

  for(int i = 1; i <= m; ++i) {
    int a, b;
    cin >> a >> b;
    G[a].push_back(b);
    ++EnDeg[b];
  }

  for(int i = 1; i <= n; ++i) {
    if(!EnDeg[i] and !used[i]) {
      Dfs(i);
      toposort.push_back(i);
    }
  }

  reverse(toposort.begin(), toposort.end());

  for(auto it: toposort) {
    cout << it << ' ';
  }

  return 0;
}