Cod sursa(job #3236715)

Utilizator Sebi_RipaSebastian Ripa Sebi_Ripa Data 30 iunie 2024 16:54:20
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.69 kb
#include <fstream>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

ifstream cin("sortaret.in");
ofstream cout("sortaret.out");

vector <int> adjt[50005];
vector <int> adjf[50005];
queue <int> q;

int main() {
	int n, m;
	cin >> n >> m;
	for (int i = 1; i <= m; i++) {
		int x, y;
		cin >> x >> y;
		adjt[x].push_back(y);
		adjf[y].push_back(x);
	}
	for (int i = 1; i <= n; i++) {
		if (adjf[i].empty())
			q.push(i);
	}
	while (!q.empty()) {
		int node = q.front();
		q.pop();
		cout << node << ' ';
		for (auto x : adjt[node]) {
			if (adjf[x].size() == 1)
				q.push(x);
			adjf[x].erase(find(adjf[x].begin(), adjf[x].end(), node));
		}
	}
}