Cod sursa(job #2199690)

Utilizator emiemiEmi Necula emiemi Data 28 aprilie 2018 18:48:25
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.71 kb
#include <fstream>
#include <vector>
#include <queue>

using namespace std;
ifstream f("sortaret.in");
ofstream g("sortaret.out");

int nr[50001];
vector<int> v[50001];
int sol[50001];

int main() {
	int i, x, y;
	int n, m;
	f >> n >> m;

	for (i = 1; i <= m; ++i) {
		f >> x >> y;
		++nr[x];
		v[y].push_back(x);
	}

	queue<int> q;
	for (i = 1; i <= n; ++i)
		if (nr[i] == 0)
			q.push(i);

	int p = 0;
	while (!q.empty()) {
		x = q.front();
		q.pop();
		y = v[x].size();
		for (i = 0; i < y; ++i) {
			--nr[v[x][i]];
			if (nr[v[x][i]] == 0) {
				q.push(v[x][i]);
			}
		}
		sol[p] = x;
		++p;
	}

	for (i = n - 1; i >= 0; --i)
		g << sol[i] << ' ';
	g << '\n';

	return 0;
}