Cod sursa(job #3199375)

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

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

void toposort(std::vector<node>& vec) {
	std::queue<dt> free;
	for(dt i = 1; i < vec.size(); i++)
		if(vec[i].in_deg == 0) free.emplace(i);

	while(!free.empty()) {
		auto& nod = vec[free.front()];
		std::cout << free.front() << ' ';
		free.pop();

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

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--) {
		dt a, b; std::cin >> a >> b;
		noduri[a].emplace_back(b);
		noduri[b].in_deg++;
	}

	noduri[0].in_deg = -1;
	toposort(noduri);
	return 0;
}