Cod sursa(job #196096)

Utilizator toni2007Pripoae Teodor Anton toni2007 Data 24 iunie 2008 15:20:58
Problema Sortare topologica Scor 20
Compilator c Status done
Runda Arhiva educationala Marime 1.12 kb
#include <stdio.h>
#include <stdlib.h>
#define N 50010
int *cine[N],cati[N],n,m;
int nr,T[N];
int vizitat[N];
void scan(void){
     int i,x,y;
     freopen("sortaret.in","r",stdin);
     freopen("sortaret.out","w",stdout);
     scanf("%d%d",&n,&m);
     for (i=1;i<=m;++i){
         scanf("%d%d",&x,&y);
         ++cati[x];
     }
     fclose(stdin);
     for (i=1;i<=n;++i){
         cine[i]=(int*)malloc(cati[x]*sizeof(int)+4);
         cati[i]=0;
     }
     freopen("sortaret.in","r",stdin);
     scanf("%d%d",&n,&m);
     for (i=1;i<=m;++i){
         scanf("%d%d",&x,&y);
         ++cati[x];
         cine[x][cati[x]]=y;
     }
}
void dfs(int x){
     int i;
     vizitat[x]=1;
     for (i=1;i<=cati[x];++i)
         if (!vizitat[cine[x][i]])
            dfs(cine[x][i]);
     T[++nr]=x;
}
void t_sort(void){
     int i;
     for (i=1;i<=n;++i)
         if (!vizitat[i])
            dfs(i);
}

void print(void){
     int i;
     for (i=n;i;--i)
         printf("%d ",T[i]);
     fclose(stdin);
     fclose(stdout);
     exit(0);
}
int main(void){
    scan();
    t_sort();
    print();
}