Cod sursa(job #1398820)

Utilizator paul-gPaul Grigoras paul-g Data 24 martie 2015 13:36:13
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.73 kb
#include <fstream>
#include <vector>
#include <deque>

using namespace std;

int main(int argc, char *argv[]) {
  ifstream f{"sortaret.in"};
  ofstream g{"sortaret.out"};

  int n, m;
  f >> n;
  f >> m;

  vector<int> edge[n];
  vector<int> degree(n, 0);

  for (int i = 0; i < m; ++i) {
    int s, d;
    f >> s >> d;
    s--, d--;
    edge[s].push_back(d);
    degree[d]++;
  }

  deque<int> sources;
  for (int i = 0; i < n; ++i) {
    if (degree[i] == 0)
      sources.push_back(i);
  }

  while (!sources.empty()) {
    int source = sources.back(); sources.pop_back();
    g << source + 1<< " ";
    for (auto d : edge[source]) {
      degree[d]--;
      if (degree[d] == 0) {
        sources.push_back(d);
      }
    }
  }


  return 0;
}