Cod sursa(job #144419)

Utilizator devilkindSavin Tiberiu devilkind Data 27 februarie 2008 16:50:53
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.68 kb
#include <stdio.h>
#include <vector>

using namespace std;

#define NMAX 100000
#define pb push_back
#define sz size()

vector<int> G[NMAX];

long int gin[NMAX];
long int cd[NMAX];
long int i,j,k,n,m,x,y;

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

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

	for (i=1;i<=m;i++)
		{
		scanf("%ld %ld",&x,&y);
		G[x].pb(y);
		gin[y]++;
		}
	
	for (i=1;i<=n;i++)
		if (gin[i]==0) cd[++cd[0]]=i;

	long int nod;

	for (i=1;i<=cd[0];i++)		
		{
			nod=cd[i];
			for (j=0;j<G[nod].sz;j++)
				{
				gin[ G[nod][j] ]--;
				if (gin[ G[nod][j]]==0) cd[++cd[0]]=G[nod][j];
				}
		}

	for (i=1;i<=n;i++)
		printf("%ld ",cd[i]);

	return 0;
}