Cod sursa(job #144455)

Utilizator pauldbPaul-Dan Baltescu pauldb Data 27 februarie 2008 17:58:02
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.64 kb
#include <stdio.h>
#include <vector>

using namespace std;

#define maxn 50010

int n,m,l;
int g[maxn],cost[maxn],s[maxn];
vector <int> a[maxn];

int main()
{
	freopen("sortaret.in","r",stdin);
	freopen("sortaret.out","w",stdout);

	scanf("%d %d ",&n,&m);

	int i,j,x,y;

	for (i=1;i<=m;i++)
	{
		scanf("%d %d ",&x,&y);
		a[y].push_back(x);
		cost[x]++;
	}

	for (i=1;i<=n;i++) g[i] = a[i].size();

	for (i=1;i<=n;i++)
		if (cost[i] == 0) s[++l] = i;

	for (i=1;i<=l;i++) 
		for (j=0;j<g[s[i]];j++)
		{
			cost[a[s[i]][j]]--;

			if (cost[a[s[i]][j]] == 0) s[++l] = a[s[i]][j];
		}

	for (i=l;i>0;i--) printf("%d ",s[i]);
	printf("\n");

	return 0;
}