Cod sursa(job #3300820)

Utilizator MihaiZ777MihaiZ MihaiZ777 Data 19 iunie 2025 12:16:43
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.17 kb
#include <algorithm>
#include <cmath>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <vector>
#include <fstream>
#include <cstring>
using namespace std;

#define fast_io ios::sync_with_stdio(0); cin.tie(0); do{}while(0)
typedef long long ll;

const int MAXN = 5e5 + 5;

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

int n, m;
vector<int> graph[MAXN];
int into[MAXN];
queue<int> toProcess;
int processedCount;
vector<int> sorted;

void ReadData() {
	fin >> n >> m;
	int a, b;
	for (int i = 0; i < m; i++) {
		fin >> a >> b;
		graph[a].push_back(b);
		into[b]++;
	}
}

void BuildInitialZeroInto() {
	for (int i = 1; i <= n; i++) {
		if (into[i]) {
			continue;
		}
		toProcess.push(i);
	}
}

void Kahn() {
	while (!toProcess.empty()) {
		int node = toProcess.front();
		toProcess.pop();
		sorted.push_back(node);

		for(int x : graph[node]) {
			into[x]--;
			if (into[x] == 0) {
				toProcess.push(x);
			}
		}
	}
}

void Solve() {
	BuildInitialZeroInto();
	Kahn();
	for (int x : sorted) {
		fout << x << ' ';
	}
	fout << '\n';
}

int main() {
		ReadData();
		Solve();
		return 0;
}