Cod sursa(job #3215255)

Utilizator andrei_C1Andrei Chertes andrei_C1 Data 14 martie 2024 19:41:11
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.6 kb
#include <bits/stdc++.h>
int main() {
	using namespace std;
	ifstream fin("sortaret.in");
	ofstream fout("sortaret.out");
	int n, m;
	fin >> n >> m;
	vector<vector<int>> adj(n);
	vector<int> in(n);
	for(int i = 0; i < m; i++) {
		int u, v;
		fin >> u >> v;
		u--; v--;
		adj[u].emplace_back(v);
		in[v]++;
	}
	priority_queue<int, vector<int>, greater<int>> pq;
	for(int u = 0; u < n; u++) {
		if(!in[u]) {
			pq.emplace(u);
		}
	}
	while(!pq.empty()) {
		int u = pq.top();
		pq.pop();
		fout << u + 1 << " ";
		for(const auto &v: adj[u]) {
			in[v]--;
			if(!in[v]) {
				pq.emplace(v);
			}
		}
	}
	return 0;
}