Cod sursa(job #469997)

Utilizator bugyBogdan Vlad bugy Data 10 iulie 2010 13:26:34
Problema Sortare topologica Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.95 kb
#include<stdio.h>
#include<stdlib.h>
#define dim 500005
using namespace std;

int n,m,x,y,i,*A[dim],viz[dim],postordine[dim],nr,j;

FILE *f=fopen("sortaret.in","r"), *g=fopen("sortaret.out","w");

void citire()
{ 
	fscanf(f,"%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<=m;i++)
{
	fscanf(f,"%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;
	
	A[y][0]++;
	A[y]=(int *)realloc(A[y], (A[y][0]+1)*sizeof(int));
	A[y][A[y][0]]=x;
	/*
	A[x][0]++;
		A[x][ A[x][0] ]=y;
		
	A[y][0]++;
		A[y][ A[y][0] ]=x;
	*/
}	

}

void DFS(int x)
{
int i;
	viz[x]=1;
	for(i=1;i<=A[x][0];i++)
		if(!viz[A[x][i]])
			DFS(A[x][i]);
	postordine[++nr]=x;
}


int main()
{

citire();
for(j=1;j<=n;j++)
	if(!viz[j])
		DFS(j);
for(i=n;i>=1;i--)
	fprintf(g,"%d ",postordine[i]);
fprintf(g,"\n");
fclose(f);
fclose(g);
	
	
return 0;
}