Cod sursa(job #2797577)

Utilizator game_difficultyCalin Crangus game_difficulty Data 10 noiembrie 2021 10:21:30
Problema Sortare topologica Scor 90
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.82 kb
#include <fstream>
#include <algorithm>
#include <vector>

using namespace std;

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

int v[50005];
vector<int> graf[50005];
bool isFirst[50005];

void go(int i, int k = 0) {
	v[i] = max(v[i], k + 1);
	for (int nod : graf[i]) {
		go(nod, k + 1);
	}
}

int main() {
	int n, m;
	cin >> n >> m;
	for (int i = 1; i <= m; i++) {
		int x, y;
		cin >> x >> y;
		isFirst[y] = 1;
		graf[x].push_back(y);
	}
	vector<int> first;
	for (int i = 1; i <= n; i++) {
		if (isFirst[i]) {
			first.push_back(i);
			v[i] = 1;
		}
	}
	for (int f : first) {
		go(f);
	}
	vector<pair<int, int>> nr;
	for (int i = 1; i <= n; i++) {
		nr.push_back({ v[i], i });
	}
	sort(nr.begin(), nr.end());
	for (auto i : nr) {
		cout << i.second << ' ';
	}
	return 0;
}