Cod sursa(job #159970)

Utilizator raduzerRadu Zernoveanu raduzer Data 14 martie 2008 16:24:25
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.62 kb
#include <stdio.h>
#include <vector>
using namespace std;

int n,m,z,b[50010],c[50010],r[50010],x,y;
vector <int> a[50010];

int main()
{
	freopen("sortaret.in","r",stdin);
	freopen("sortaret.out","w",stdout);
	scanf("%d%d",&n,&m);
	int i,j;
	for (i=1; i<=m; ++i) 
	{
		scanf("%d%d",&x,&y);
		a[y].push_back(x);
		++c[x];
	}
	for (i=1; i<=n; ++i) 
	{
		b[i]=a[i].size();
		if (c[i]==0) r[++z]=i;
	}
	for (i=1; i<=z; ++i)
	{
		for (j=0; j<b[r[i]]; ++j)
		{
			--c[a[r[i]][j]];
			if (c[a[r[i]][j]]==0) r[++z]=a[r[i]][j];
		}
	}
	for (i=n; i>0; --i) printf("%d ",r[i]);
	printf("\n");
	return 0;
}