Cod sursa(job #495409)

Utilizator IgnitionMihai Moraru Ignition Data 25 octombrie 2010 02:09:01
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.91 kb
#include <stdio.h>
#include <list>

using namespace std;

#define MN (50000)

list<int> g[MN];
int depth[MN];
int sol[MN], N_sol;

int dfs(int node)
{
	if(depth[node] > -1)
		return depth[node];
	depth[node] = 0;
	for(list<int>::iterator j = g[node].begin(); j != g[node].end(); ++j)
		if(dfs(*j)+1 > depth[node])
			depth[node] = dfs(*j)+1;
	sol[N_sol++] = node;
	return depth[node];
}

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

	int N, M, i, j, k;

	scanf("%d %d", &N, &M);

	for(i = 0; i < N; ++i)
		depth[i] = -1;

	for(k = 0; k < M; ++k) {
		scanf("%d %d", &i, &j);
		--i, --j;
		g[i].push_back(j);
	}

	/*
	for(i = 0; i < N; ++i) {
		printf("%d:", i+1);
		for(list<int>::iterator j = g[i].begin(); j != g[i].end(); ++j)
			printf(" %d", *j+1);
		printf("\n");
	}
	*/

	for(i = 0; i < N; ++i)
		dfs(i);

	for(i = N_sol-1; i >= 0; --i)
		printf("%d ", sol[i]+1);

	return 0;
}