Cod sursa(job #158150)

Utilizator mike4problemsRadu Gabriel mike4problems Data 13 martie 2008 14:35:10
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.52 kb
#include<fstream>
using namespace std;

#define N 50001
#define M 100001

ifstream f("sortaret.in");
ofstream g("sortaret.out");

int n,m,viz[N];
int start[N],list[M][2];
int sol[N],id_sol;

void df(int k)
{
	viz[k]=1;
	for(int i=start[k];i;i=list[i][0])
		if(!viz[list[i][1]]) df(list[i][1]);
	sol[++id_sol]=k;
}

int main()
{
	int i,j,k;
	f>>n>>m;
	while(m)
	{
		f>>i>>j;
		list[m][1]=j;
		list[m][0]=start[i];
		start[i]=m--;
	}
	for(i=1;i<=n;i++)
		if(!viz[i]) df(i);
	for(i=id_sol;i>0;i--)
		g<<sol[i]<<' ';
	g<<'\n';
	return 0;
}