Cod sursa(job #1580350)

Utilizator PopoviciRobertPopovici Robert PopoviciRobert Data 25 ianuarie 2016 19:59:14
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.71 kb
#include <cstdio>
#define MAXN 50000
#define MAXM 100000
int nod[MAXM+1],ind[MAXN+1],next[MAXM+1],vf[MAXN+1],top[MAXN],nr=0;
void DFS(int x){
     int poz=ind[x];
     vf[x]=1;
     while(poz>0){
         if(vf[nod[poz]]==0)
            DFS(nod[poz]);
         poz=next[poz];
     }
     top[nr++]=x;
}
int main(){
    FILE*fi,*fout;
    int i,n,m,x;
    fi=fopen("sortaret.in" ,"r");
    fout=fopen("sortaret.out" ,"w");
    fscanf(fi,"%d%d" ,&n,&m);
    for(i=1;i<=m;i++){
        fscanf(fi,"%d%d" ,&x,&nod[i]);
        next[i]=ind[x];
        ind[x]=i;
    }
    for(i=1;i<=n;i++)
       if(vf[i]==0)
          DFS(i);
    for(i=n-1;i>=0;i--)
       fprintf(fout,"%d " ,top[i]);
    fclose(fi);
    fclose(fout);
    return 0;
}