Cod sursa(job #401085)

Utilizator laserbeamBalan Catalin laserbeam Data 22 februarie 2010 13:29:19
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.76 kb
#include<cstdio>
#include<cstdlib>
#include<list>
#include<queue>
using namespace std;

#define NMAX 50003

list<int> G[NMAX];
queue<int> Q;
int n,m;
int deg[NMAX],viz[NMAX];

int main()
{
	freopen("sortaret.in","r",stdin);
	freopen("sortaret.out","w",stdout);
	
	scanf("%d %d",&n,&m);
	int x,y;
	for (;m;--m)
	{
		scanf("%d %d",&x,&y);
		G[x].push_back(y);
		deg[y]++;
	}
	
	for (int i = 1; i <= n; ++i)
	{
		if (deg[i] == 0) Q.push(i), viz[i] = 1;
	}
	
	int now;
	while (!Q.empty())
	{
		now = Q.front();
		printf("%d ", now);
		Q.pop();
		for (list<int>::iterator it = G[now].begin(); it != G[now].end(); ++it)
		{
			deg[*it]--;
			if (deg[*it] == 0 && !viz[*it]) Q.push(*it), viz[*it] = 1;
		}
	}
	
	return EXIT_SUCCESS;
}