Cod sursa(job #590082)

Utilizator lily3Moldovan Liliana lily3 Data 15 mai 2011 14:59:56
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.58 kb
#include<fstream>
using namespace std;

int i,j,n,m,*a[50001],p[50001],x,y,v[50001],nr=0;
void dfs(int x)
{
	int i;
	v[x]=1;
	for(i=1;i<=a[x][0];i++)
		if(!v[a[x][i]])
			dfs(a[x][i]);
		p[++nr]=x;
}
int main()
{
	ifstream f("sortaret.in");
	ofstream g("sortaret.out");
	f>>n>>m;
	for(i=1;i<=n;i++)
	{
		a[i]=(int *)realloc(a[i],sizeof(int));
		a[i][0]=0;
	}
	while(f>>x>>y)
	{
		a[x][0]++;
		a[x]=(int *)realloc(a[x],(a[x][0]+1)*sizeof(int));
		a[x][a[x][0]]=y;
	}
	for(i=1;i<=n;i++)
		if(!v[i])
			dfs(i);
		for(i=n;i>=1;i--)
			g<<p[i]<<" ";
		return 0;
}