Cod sursa(job #2485288)

Utilizator stef2003Bud Stefan stef2003 Data 1 noiembrie 2019 11:30:11
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.83 kb
#include <iostream>
#include <cstdio>

using namespace std;

int lst[50001], q[50001], d[50001], nrp[50001];
int vf[200001], urm[200001], nr;

void adauga(int x, int y) {
  nr++;
  vf[nr]=y;
  urm[nr]=lst[x];
  lst[x]=nr;
}

int main() {
  FILE *fin, *fout;
  int i, st, dr, x, y, p, n, m, a, b;
  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);
    nrp[b]++;
    adauga(a,b);
  }
  for(i=1;i<=50001;i++)
    d[i]=-1;
  st=0;
  dr=-1;
  for(i=1;i<=n;i++) {
    if(nrp[i]==0) {
      dr++;
      q[dr]=i;
      d[i]=0;
    }
  }
  while(st<=dr) {
    x=q[st++];
    fprintf(fout ,"%d ",x);
    for(p=lst[x];p!=0;p=urm[p]) {
      y=vf[p];
      nrp[y]--;
      if(nrp[y]==0)
        q[++dr]=y;
    }
  }
  fclose( fin );
  fclose( fout );
  return 0;
}