Cod sursa(job #1909495)

Utilizator lflorin29Florin Laiu lflorin29 Data 7 martie 2017 12:54:23
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.94 kb
#include <bits/stdc++.h>

using namespace std;

const int nMax = 50007;

int n, m, gin[nMax];
vector<int>tra[nMax];

void Citire() {
	scanf("%d%d", &n, &m);

	for (int i = 1, from, to; i <= m; ++i) {
		scanf("%d%d", &from, &to);
		tra[to].push_back(from);
		gin[from] ++;
	}
}

vector<int>Sortaretopo() {
	queue<int>q;
	vector<int>sol;

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

	while (!q.empty()) {
		int nod = q.front();
		q.pop();
		sol.push_back(nod);

		for (const auto& itr : tra[nod]) {
			gin[itr]--;

			if (!gin[itr]) {
				q.push(itr);
			}
		}
	}
	reverse(begin(sol), end(sol));

	return sol;
}

void print(const vector<int>&that) {
	for (const auto& itr : that)
		printf("%d ", itr);

	printf("\n");
}

int main() {
	freopen("sortaret.in", "r", stdin);
	freopen("sortaret.out", "w", stdout);

	Citire();
	auto ordine = Sortaretopo();
	print(ordine);
	return 0;
}