Cod sursa(job #3199383)

Utilizator robeteaRobert Cristea robetea Data 1 februarie 2024 15:57:13
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.81 kb
#include <alloca.h>
#include <bits/stdc++.h>

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

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

	while(free != end) {
		auto& nod = vec[*free];
		std::cout << *free << ' ';
		++free;

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

int main() {
	freopen("sortaret.in", "r", stdin);
	freopen("sortaret.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;
}