Cod sursa(job #954820)

Utilizator gabrieligabrieli gabrieli Data 30 mai 2013 08:07:02
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.64 kb
#include <cstdlib>
#include <fstream>
#include <iostream>
#include <vector>
using namespace std;

const size_t MAXN = 50010;
ifstream fin ("sortaret.in");
ofstream fout ("sortaret.out");

vector <int> G[MAXN], sol;
int inD[MAXN];

int main()
{
	int N, m;
	for (fin >> N >> m; m; --m)
	{
		int x, y;
		fin >> x >> y;
		G[x].push_back (y);
		inD[y]++;
	}

	for (int i = 1; i <= N; ++i)
		if (!inD[i])
			sol.push_back (i);

	for (size_t i = 0; i < sol.size(); ++i)
	{
		int v = sol[i];
		for (auto &n : G[v])
		{
			--inD[n];
			if (!inD[n])
				sol.push_back (n);
		}
	}

	for (auto &v : sol)
		fout << v << ' ';
	fout << endl;

	return EXIT_SUCCESS;
}