Cod sursa(job #2014369)

Utilizator ApostolIlieDanielApostol Daniel ApostolIlieDaniel Data 23 august 2017 15:20:27
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.8 kb
#include <bits/stdc++.h>

using namespace std;

const int MAXN = 50000;

int grad[MAXN + 1], sol[MAXN + 1];
vector <int> g[MAXN + 1];

int main() {
  FILE *fin, *fout;
  int n, m, i, a, b, x, f, j;
  vector<int>::iterator it;
  fin = fopen ("sortaret.in", "r");
  fout = fopen ("sortaret.out", "w");
  fscanf (fin, "%d%d", &n, &m);
  for (i = 1; i <= m; i++) {
    fscanf (fin, "%d%d", &a, &b);
    g[a].push_back(b);
    grad[b]++;
  }
  for(i = 1; i <= n; i++)
    if(grad[i] == 0)
      sol[++sol[0]] = i;
  for(i = 1; i <= n; i++) {
    x = sol[i];
    f = g[x].size();
    for(it = g[x].begin(); it != g[x].end(); ++it) {
      grad[*it]--;
      if(grad[*it] == 0)
        sol[++sol[0]] = *it;
    }
  }
  for (i = 1; i <= n; i++)
    fprintf (fout, "%d ", sol[i]);
  return 0;
}