Cod sursa(job #431150)

Utilizator slayer4uVictor Popescu slayer4u Data 31 martie 2010 18:36:18
Problema Sortare topologica Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.73 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[i].size(); ++j)
		{
			--degree[graf[i][j]];
			if (!degree[graf[i][j]])
				rez.push_back(graf[i][j]);
		}
	}

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