Cod sursa(job #600543)

Utilizator noobHikaru noob Data 2 iulie 2011 11:42:41
Problema Sortare topologica Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.59 kb
#include <iostream>
#include <stdio.h>
#include <stdlib.h>

void visit(int edge,int * * vertices,int m,
           int * visited,int & posVis,int * sortedL,int & posSort);
           
int inVect(int nr,int * vect,int len);

int main()
{
 FILE * fpin,* fpout;
 fpin=fopen("sortaret.in","r");
 fpout=fopen("sortaret.out","w");
 
 int n,m;
 fscanf(fpin,"%d",&n);
 fscanf(fpin,"%d",&m);
 
 int * * vertices=(int * *)calloc(m,sizeof(int*));
 int i;
 for (i=0;i<m;i++)
  vertices[i]=(int *)calloc(2,sizeof(int));
 
 for (i=0;i<m;i++)
  {fscanf(fpin,"%d",&vertices[i][0]);
   fscanf(fpin,"%d",&vertices[i][1]);
   vertices[i][0]--;vertices[i][1]--;}
 fclose(fpin);
 
 int * sortedL=(int *)calloc(n,sizeof(int));
 int * freeEdges=(int *)calloc(n,sizeof(int));
 int * visited=(int *)calloc(n,sizeof(int));
 int posVis=0,posSort=0;
 
 
 
 for (i=0;i<n;i++) freeEdges[i]=i;
 for (i=0;i<m;i++) freeEdges[vertices[i][1]]=-1;
 
 for (i=0;i<n;i++)
  if (freeEdges[i]!=-1) visit(i,vertices,m,visited,posVis,sortedL,posSort);
   
 
 for (i=0;i<n;i++) fprintf(fpout,"%d ",sortedL[i]+1);
 fclose(fpout);
 
 return 0;
}

void visit(int edge,int * * vertices,int m,
           int * visited,int & posVis,int * sortedL,int & posSort)
{
 if (!inVect(edge,visited,posVis))
  {visited[posVis]=edge;posVis++;}
 
 for (int i=0;i<m;i++)
 {
  if (vertices[i][0]==edge) 
   visit(vertices[i][1],vertices,m,visited,posVis,sortedL,posSort);
 }
 
 sortedL[posSort]=edge;posSort++;
}

int inVect(int nr,int * vect,int len)
{
 for (int i=0;i<len;i++)
  if (nr==vect[i]) return 1;
 return 0;
}