Cod sursa(job #2195937)

Utilizator WebDesignbyTMGhiorghiu Ioan-Viorel WebDesignbyTM Data 17 aprilie 2018 20:14:23
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.6 kb
#define DM 50001
#include <fstream>
#include <queue>
#include <vector>
using namespace std;

ifstream fi ("sortaret.in");
ofstream fo ("sortaret.out");
int n, m, a, b, apr[DM];
queue <int> q;
vector <int> v[DM], sol;

void propag()
{
	for (int i = 1; i <= n; ++i)
		if (!apr[i])
			q.push(i);
	while (!q.empty())
	{
		a = q.front();
		q.pop();
		for (auto i:v[a])
		{
			--apr[i];
			if (!apr[i])
				q.push(i);
		}
		sol.push_back(a);
	}
}

int main()
{
	fi >> n >> m;
	for (int i = 1; i <= m; ++i)
	{
		fi >> a >> b;
		v[a].push_back(b);
		++apr[b];
	}
	propag();
	for (auto i:sol)
		fo << i << ' ';
	return 0;
}