Cod sursa(job #3199354)

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

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

void toposort(std::vector<node>& vec) {
	std::queue<int> free;
	for(int 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--) {
		int a, b; std::cin >> a >> b;
		noduri[a].emplace_back(b);
		noduri[b].in_deg++;
	}

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