Cod sursa(job #156730)

Utilizator razvi9Jurca Razvan razvi9 Data 12 martie 2008 18:37:08
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.55 kb
#include<cstdio>
#include<vector>
using namespace std;
vector<int> a[50001];
int gr[50001],i,j,n,m,x,y,s[50001];
int main()
{
	freopen("sortaret.in","r",stdin);
	freopen("sortaret.out","w",stdout);
	scanf("%d %d",&n,&m);
	for(i=1;i<=m;++i){
		scanf("%d %d",&x,&y);
		a[x].push_back(y);gr[y]++;}

	for(i=1;i<=n;i++)
		if(gr[i]==0) s[++s[0]]=i;
	for(i=1;i<=n;i++)
	{
		x=s[i];
		for(j=0;j<a[x].size();++j){
			y=a[x][j];
			gr[y]--;
			if(gr[y]==0) s[++s[0]]=y;}
	}
	for(i=1;i<=n;++i)
		printf("%d ",s[i]);
	fclose(stdout);
	return 0;
}