Cod sursa(job #431165)

Utilizator slayer4uVictor Popescu slayer4u Data 31 martie 2010 18:46:36
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.77 kb
#include <cstdio>
#include <vector>
using namespace std;

#define NMAX 50050

vector <int> graf[NMAX], rez;
long a, b, m, n, degree[NMAX];

int main()
{
	freopen ("sortaret.in", "rt", stdin);
	freopen ("sortaret.out", "wt", stdout);

	scanf("%ld %ld", &n, &m);
	for (long i = 1; i <= m ; ++i)
	{
		scanf("%ld %ld", &a, &b);
		graf[a].push_back(b);
		++degree[b];
	}

	for (long i = 1; i <= n; ++i)
		if (!degree[i])
			rez.push_back(i);

	for (long i = 1; i <= n; ++i)
	{
		for (long j = 0; j < graf[rez[i - 1]].size(); ++j)
		{
			--degree[graf[rez[i - 1]][j]];
			if (!degree[graf[rez[i - 1]][j]])
				rez.push_back(graf[rez[i - 1]][j]);
		}
	}

	for (long i = 0; i < rez.size(); ++i)
		printf("%ld ", rez[i]);
	printf("\n");
	
	return 0;
}