Cod sursa(job #3136799)

Utilizator Uriesu_IuliusUriesu Iulius Uriesu_Iulius Data 8 iunie 2023 17:26:53
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.9 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <set>
#include <stack>
#include <queue>

using namespace std;

ifstream fin("sortaret.in");
ofstream fout("sortaret.out");

const int mxN = 5e4 + 5;
int n, m;
bool vis[mxN];
vector<int> adj[mxN];
int inDegree[mxN];

void readInput() {
	fin >> n >> m;
	for (int i = 0; i < m; i++) {
		int u, v;
		fin >> u >> v;
		adj[u].push_back(v);
		inDegree[v]++;
	}
}

void predecessorCounting() {
	queue<int> Q;
	for (int i = 1; i <= n; i++) {
		if (inDegree[i] == 0) {
			Q.push(i);
		}
	}

	vector<int> topSort;

	while (!Q.empty()) {
		int u = Q.front();
		Q.pop();

		topSort.push_back(u);
		for (auto v : adj[u]) {
			inDegree[v]--;
			if (inDegree[v] == 0) {
				Q.push(v);
			}
		}
	}

	for (auto u : topSort) {
		fout << u << " ";
	}
}

int main() {

	readInput();
	predecessorCounting();
	return 0;
}