Cod sursa(job #186846)

Utilizator Spike7d8Cristian Varvara Spike7d8 Data 28 aprilie 2008 20:34:44
Problema Sortare topologica Scor 80
Compilator cpp Status done
Runda Arhiva educationala Marime 0.83 kb
#define _CRT_SECURE_NO_WARNINGS

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


#define N 50176

vector <int> muchie[N], solutie, lista;
int grad[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.push_back(i);

	while (lista.size())
	{
		int nod = lista[0];
		solutie.push_back(nod);
		lista.erase(lista.begin());

		for (int i = 0; i < (int)muchie[nod].size(); i++)
			if (!(--grad[muchie[nod][i]]))
				lista.push_back(muchie[nod][i]);
	}

	for (int i = 0; i < (int)solutie.size(); i++)
		printf("%d ", solutie[i]);
	printf("\n");


	return 0;
}