Cod sursa(job #3297072)

Utilizator raresgoidescuGoidescu Rares-Stefan raresgoidescu Data 20 mai 2025 22:15:01
Problema Sortare topologica Scor 90
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.94 kb
#include <iostream>
#include <queue>
#include <vector>

const int MAXN = 50000;

int n, m;
std::vector<int> adj[MAXN];
int in_degree[MAXN];
std::vector<int> topo_order;

void kahn_bfs()
{
	std::queue<int> q;

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

	while (!q.empty()) {
		int u = q.front();
		q.pop();
		topo_order.push_back(u);

		for (int v : adj[u]) {
			in_degree[v]--;
			if (in_degree[v] == 0) {
				q.push(v);
			}
		}
	}
}

int main(void)
{
#ifndef LOCAL
	freopen("sortaret.in", "r", stdin);
	freopen("sortaret.out", "w", stdout);
#endif

	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);

	std::cin >> n >> m;

	for (int i = 0; i < m; ++i) {
		int u, v;

		std::cin >> u >> v;

		adj[u].push_back(v);

		in_degree[v]++;
	}

	kahn_bfs();

	for (size_t i = 0; i < topo_order.size(); ++i) {
		std::cout << topo_order[i] << (i == topo_order.size() - 1 ? "" : " ");
	}
	std::cout << '\n';

	return 0;
}