Cod sursa(job #627580)

Utilizator paul24090FMI - Balauru Paul paul24090 Data 30 octombrie 2011 10:33:42
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.73 kb
#include <cstdio>
#include <list>

using namespace std;

int n,m,nr,v[50002],nrTati[50002],postordine[50002];
list<int> l[50002];

void citire()
{
	int x,y;
	scanf("%d %d",&n,&m);
	for(int i=1;i<=m;i++)
	{
		scanf("%d %d",&x,&y);
		l[x].push_back(y);
		nrTati[y]++;
	}
}

void dfs(int k)
{
	v[k]=1;
	list<int>::iterator it;
	for(it=l[k].begin();it!=l[k].end();++it)
		if(!v[*it])
			dfs(*it);
	nr++;
	postordine[nr]=k;
}

void afisare()
{
	for(int i=n;i>=1;i--)
		printf("%d ",postordine[i]);
	printf("\n");
}

int main()
{
	freopen("sortaret.in","rt",stdin);
	freopen("sortaret.out","wt",stdout);
	citire();
	for(int i=1;i<=n;i++)
		if(v[i]==0 && nrTati[i]==0)
			dfs(i);
	afisare();
	return 0;
}