Cod sursa(job #343277)

Utilizator bog29Antohi Bogdan bog29 Data 25 august 2009 13:32:18
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.66 kb
#include<fstream>
#define dmax 50003
using namespace std;
ifstream in("sortaret.in");
ofstream out("sortaret.out");
int n,m,po[dmax],crt,viz[dmax];
int* g[dmax];
int dfs(int k)
{	int i;
	viz[k]=1;
	for(i=1;i<=g[k][0];i++)
		if(viz[g[k][i]]==0)
			dfs(g[k][i]);
	crt++;
	po[crt]=k;	
}
int main()
{	int i,a,b;
	in>>n>>m;
	for(i=1;i<=n;i++)
	{	g[i]=(int*)realloc(g[i],sizeof(int));
		g[i][0]=0;
	}
	for(i=1;i<=m;i++)
	{	in>>a>>b;	
		g[a][0]++;
		g[a]=(int*)realloc(g[a],(g[a][0]+1)*sizeof(int));
		g[a][g[a][0]]=b;
	}
	in.close();
	for(i=1;i<=n;i++)
		if(viz[i]==0)
			dfs(i);
	for(i=n;i>0;i--)
		out<<po[i]<<" ";
	out.close();
	return 0;
}