Cod sursa(job #3199351)

Utilizator robeteaRobert Cristea robetea Data 1 februarie 2024 15:38:18
Problema Sortare topologica Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.93 kb
#include <bits/stdc++.h>

struct node : std::vector<int> {
	int in_deg = 0;
};

std::vector<int> toposort(std::vector<node> vec, int start) {
	std::queue<int> free; free.push(start);
	std::vector<int> out; out.reserve(vec.size());

	while(!free.empty()) {
		auto& nod = vec[free.front()];
		out.emplace_back(free.front());
		free.pop();

		//std::random_shuffle(nod.begin(), nod.end());
		for(auto v : nod) {
			if(--vec[v].in_deg == 0) free.push(v);
		}
	}

	return out;
}

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

	int n, m; std::cin >> n >> m;
	std::vector<node> noduri(n + 1);
	while(m--) {
		int a, b; std::cin >> a >> b;
		noduri[a].emplace_back(b);
		noduri[b].in_deg++;
	}

	noduri[0].reserve(n);
	for(int i = 1; i <= n; i++) {
		noduri[i].in_deg++;
		noduri[0].emplace_back(i);
	}

	auto sortare = toposort(noduri, 0);
	for(int i = 1; i <= n; i++) std::cout << sortare[i] << ' ';
	return 0;
}