Cod sursa(job #144815)

Utilizator filipbFilip Cristian Buruiana filipb Data 27 februarie 2008 23:29:35
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.61 kb
#include <stdio.h>
#include <vector>

using namespace std;

#define NMax 50005

int N, M, uz[NMax], t[NMax], timp;
vector<int> G[NMax];

void df(int nod)
{
	int i, x, sz;

	uz[nod] = 1;
	for (sz = G[nod].size(), i = 0; i < sz; ++i)
		if (!uz[x = G[nod][i]])
			df(x);
	t[++timp] = nod;
}

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

	scanf("%d %d", &N, &M);
	for (; M; --M)
	{
		scanf("%d %d", &j, &k);
		G[j].push_back(k);
	}

	for (i = 1; i <= N; i++)
		if (!uz[i])
			df(i);
	
	for (i = N; i; --i)
		printf("%d ", t[i]);
	printf("\n");
	
	return 0;
}