Cod sursa(job #2522637)

Utilizator andra1782Andra Alazaroaie andra1782 Data 12 ianuarie 2020 19:12:47
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.81 kb
#include <stdio.h>
#include <queue>
#define MAXV 50001
#define MAXE 100001
int v[MAXV],l[MAXE],next[MAXE],g[MAXV],r[MAXV];
std::queue<int>q;
int main(){
    FILE *fin=fopen("sortaret.in","r");
    FILE *fout=fopen("sortaret.out","w");
    int n,m,i,x,y,d=1,lr=0;

    fscanf(fin,"%d%d",&n,&m);
    for(i=0; i<m; i++){
      fscanf(fin,"%d%d",&x,&y);
      l[d]=y;
      next[d]=v[x];
      v[x]=d++;
      g[y]++;
    }
    for(i=1; i<=n; i++)
      if(!g[i])
        q.push(i);
    while(!q.empty()){
      int f=q.front();
      q.pop();
      r[lr++]=f;
      i=v[f];
      while(i){
        g[l[i]]--;
        if(!g[l[i]])
          q.push(l[i]);
        i=next[i];
      }
    }
    for(i=0; i<n; i++)
      fprintf(fout,"%d ",r[i]);
    fclose(fin);
    fclose(fout);
    return 0;
}