Cod sursa(job #631905)

Utilizator mihai_bogdaannMihai Bogdan mihai_bogdaann Data 9 noiembrie 2011 21:50:49
Problema Sortare topologica Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.74 kb
#include<stdlib.h>
#include<stdio.h>

FILE * fin = fopen("sortaret.in", "r");
FILE * fout = fopen("sortaret.out", "w");

int *a[50001],i,j,n,m,sort[50001],x,y,viz[50001],nr;

void citire()
{
	fscanf(fin,"%d%d",&n,&m);
	for(i=1;i<=n;i++)
		a[i] = (int *)realloc(a[i],sizeof(int)),a[i][0]=0;
	for(i=1;i<=n;i++)
	{
		fscanf(fin,"%d%d",&x,&y);
		a[x][0]++;
		a[x] = (int *)realloc(a[x],(a[x][0]+1)*sizeof(int));
		a[x][a[x][0]]=y;
	}
	
}

void DFS(int x)
{
	viz[x]=1;
	sort[++nr]=x;
	int j;
	for(j=1;j<=a[x][0];j++)
	{
		if(!viz[j])
			DFS(a[x][j]);
	}
	
}

void scriere()
{
	for(i=1;i<=n;i++)
		fprintf(fout,"%d ",sort[i]);
}

int main()
{
	
	citire();
	for(i=1;i<=n;i++)
		if(!viz[i])
			DFS(i);
	scriere();
}