Cod sursa(job #197298)

Utilizator toni2007Pripoae Teodor Anton toni2007 Data 3 iulie 2008 12:18:04
Problema Sortare topologica Scor 100
Compilator c Status done
Runda Arhiva educationala Marime 1.15 kb
#include <stdio.h>
#include <stdlib.h>
#define N 50010
int *cine[N],cati[N],n,m;
int nr,T[N];
int vizitat[N];
int grad[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];
         cine[x]=(int*)realloc(cine[x],cati[x]*sizeof(int)+4);
         cine[x][cati[x]]=y;
         ++grad[y];
     }
}
int queue[N],p,u;
void insert(int i){
	queue[u++]=i;
}
int push(){
	printf("%d ",queue[p]);
	return queue[p++];
}
int empty(){
	if (p<u)
      return 0;
    return 1;
}
void t_sort(void){
     int i,x;
     for (i=1;i<=n;++i)
        if (!grad[i])
          insert(i);
     while (!empty()){
        x=push();
        for (i=1;i<=cati[x];++i){
           --grad[cine[x][i]];
           if (!grad[cine[x][i]])
             insert(cine[x][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();
}