Cod sursa(job #256698)

Utilizator otilia_sOtilia Stretcu otilia_s Data 12 februarie 2009 00:10:59
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.13 kb
//sortare topologica - iterativ
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define NMAX 50001
using namespace std;
int *L[NMAX],*L2[NMAX];
int Q[NMAX],grad[NMAX];
int n;

void citire()
{ int i,x,y,m;
 FILE *fin=fopen("sortaret.in","r");
 fscanf(fin,"%d%d",&n,&m);
 for (i=1;i<=n;i++)
  {L[i]=(int*)realloc(L[i],sizeof(int)); L[i][0]=0;
   L2[i]=(int*)realloc(L2[i],sizeof(int)); L2[i][0]=0;
  }
 memset(grad,0,(n+1)*sizeof(int));
 for (i=1;i<=m;i++)
  {
   fscanf(fin,"%d%d",&x,&y);
   L[x][0]++;
   L[x]=(int*)realloc(L[x],(L[x][0]+1)*sizeof(int));
   L[x][L[x][0]]=y;
   grad[x]++;
   L2[y][0]++;
   L2[y]=(int*)realloc(L2[y],(L2[y][0]+1)*sizeof(int));
   L2[y][L2[y][0]]=x;
  }
}

void rez()
{     int i,x,j;
 Q[0]=0;
 while (Q[0]<n)
  {
   for (i=1;i<=n;i++)
    if (!grad[i])
       {
	Q[++Q[0]]=i; grad[i]=-1;
	for (j=1;j<=L2[i][0];j++)
	 {
	  grad[L2[i][j]]--;
	 }
       }
  }
}

void afisare()
{int i;
 FILE *fout=fopen("sortaret.out","w");
 for (i=n;i>0;i--)
  fprintf(fout,"%d ",Q[i]);
 fclose(fout);
}

int main()
{
 citire();
 rez();
 afisare();
 return 0;
}