Cod sursa(job #650799)

Utilizator FIIGLMFIIGherasimLupascuMiron FIIGLM Data 18 decembrie 2011 23:18:59
Problema Sortare topologica Scor 0
Compilator c Status done
Runda Arhiva educationala Marime 1.29 kb
#include <stdio.h>
#include <stdlib.h>
//int a[50000][50000],viz[50000];
int N,M,nr;
int main()
{   int i,j,x,y,gasit;
    int ** a;
    int * viz;
    FILE* fin;
    FILE* fout;
    fin=fopen("sortaret.in","r");
    fout=fopen("sortaret.out","w");
    
    fscanf(fin,"%d %d ",&N,&M);
    
    a=(int**) calloc(N + 1,sizeof(int*));
    for(i=0;i<=N;i++)
               a[i] = (int*) calloc( N + 1,sizeof(int));
    viz=(int*) calloc( N + 1,sizeof(int));
    
    for(i=1;i<=M;i++)
    {  fscanf(fin,"%d%d",&x,&y);
         a[x][y]=1;
         a[0][y]++; 
    }   
    while(nr<=N)
    {  
       gasit=0;         
       for(i=1;i<=N && gasit==0;i++)
       {
           gasit=0;         
           if(!viz[i] && a[0][i]==0)
           {  gasit=1;
              viz[i]=1;
              nr++;
             fprintf(fout,"%d ",i);
            
              for(j=1;j<=N;j++)
               if(a[i][j]!=0)
                {
                  a[i][j]=0;
                  a[0][j]--;
                }
            }                 
                
       }
           
                          
                
    }
    
             
    for(i=1;i<=N;i++) free(a[i]);
    free(a);
    free(viz);
    
    fclose(fin);
    fclose(fout);  
    return 0;
}