Cod sursa(job #632024)

Utilizator laurionLaurentiu Ion laurion Data 10 noiembrie 2011 03:27:17
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.61 kb
#include<cstdio>
#include<vector>
using namespace std;
int n,m,x,y,grad_int[100000+5],Q[100000+5];
vector<int> G[50000+5];
int main()
{
	freopen("sortaret.in","r",stdin);
	freopen("sortaret.out","w",stdout);
	
	scanf("%d %d",&n,&m);
	for(int i=1;i<=m;++i)
	{
		scanf("%d %d",&x,&y);
		G[x].push_back(y);
		grad_int[y]++;
	}
	
	for(int i=1;i<=n;++i)
	{
		if(grad_int[i]==0)
			Q[++Q[0]]=i;
	}
	for(int i=1;i<=n;++i)
	{
		x=Q[i];
		for(int j=0,stop=G[x].size();j<stop;++j)
		{
			if(--grad_int[G[x][j]]==0)
				Q[++Q[0]]=G[x][j];
			
		}
		printf("%d ",x);
	}
	
	putchar('\n');
	
	return 0;
}