Cod sursa(job #186856)

Utilizator Spike7d8Cristian Varvara Spike7d8 Data 28 aprilie 2008 20:53:27
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.77 kb
#define _CRT_SECURE_NO_WARNINGS

#include <cstdio>
#include <vector>
using namespace std;


#define N 50176

vector <int> muchie[N];
int grad[N], lista[N];


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

	int n, m;
	scanf("%d%d", &n, &m);
	while (m--)
	{
		int x, y;
		scanf("%d%d", &x, &y);
		muchie[x].push_back(y);
		grad[y]++;
	}

	for (int i = 1; i <= n; i++)
		if (grad[i] == 0)
			lista[++lista[0]] = i;

	for (int i = 1; i <= n; i++)
	{
		int nod = lista[i];

		for (vector<int>::iterator it = muchie[nod].begin(); it != muchie[nod].end(); it++)
			if (!(--grad[*it]))
				lista[++lista[0]] = *it;
	}

	for (int i = 1; i <= n; i++)
		printf("%d ", lista[i]);
	printf("\n");

	return 0;
}