Cod sursa(job #2681045)

Utilizator stef2003Bud Stefan stef2003 Data 4 decembrie 2020 20:28:46
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.7 kb
#include <iostream>
#include <cstdio>
#include <vector>

using namespace std;

vector <int> v[50001];
int gri[50001], q[50001];
int main() {
  FILE *fin, *fout;
  int n, m, i, x, y, st, dr;
  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",&x,&y);
    v[x].push_back(y);
    gri[y]++;
  }
  st=0;
  dr=-1;
  for(i=1;i<=n;i++)
    if(gri[i]==0)
      q[++dr]=i;
  while(st<=dr) {
    x=q[st++];
    fprintf(fout, "%d ",x);
    for(i=0;i<v[x].size();i++) {
        gri[v[x][i]]--;
        if(gri[v[x][i]]==0)
          q[++dr]=v[x][i];
    }
  }
  fclose( fin );
  fclose( fout );
  return 0;
}