Cod sursa(job #1539541)

Utilizator pickleVictor Andrei pickle Data 30 noiembrie 2015 23:11:32
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.8 kb
#include <iostream>
#include <string>
#include <fstream>
#include <algorithm>
#include <vector>
#include <queue>

#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 incident[Nmax];

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

  int N, M, a, b;
  fin >> N >> M;
  REP(i,M) {
    fin >> a >> b;
    G[a].push_back(b);
    ++incident[b];
  }
  queue<int> Q;

  FOR(i, N) {
    if (incident[i] == 0)
      Q.push(i);
  }

  while(!Q.empty()) {
    int vertex = Q.front();
    Q.pop();
    fout << vertex << ' ';
    for(auto nbr: G[vertex]) {
      --incident[nbr];
      if(incident[nbr] == 0)
        Q.push(nbr);
    }
  }
  fout << endl;

  return 0;
}