Cod sursa(job #2916145)

Utilizator matwudemagogul matwu Data 28 iulie 2022 11:18:51
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.2 kb
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
#define EFC cin.tie(nullptr)->ios_base::sync_with_stdio(false)
int d1[5] = { 0, -1, 0, 1, 0 };
int d2[5] = { 0, 0, 1, 0, -1 };
const int mod = 666013;
const int INF = 100000000;
int d11[9] = { 0 , -1, -1, 0, 1, 1, 1, 0, -1 };
int d22[9] = { 0, 0, 1, 1, 1, 0, -1, -1, -1 };
int est[3] = { 0, -1, 0 };
int est1[3] = { 0, 0, 1 };
ifstream fin("sortaret.in");
ofstream fout("sortaret.out");


//----------------------------------

int n, m;
vector<vector<int>> liste(50001);

void top_sort() {

	vector<int> grade(n + 1);
	for (int i = 1; i <= n; i++) {
		for (auto j : liste[i]) {
			grade[j]++;
		}
	}
	int cnt = 0;
	multiset<int> s;
	for (int i = 1; i <= n; i++) {
		if (grade[i] == 0) {
			s.insert(i);
		}
	}

	vector<int> top;
	while (!s.empty()) {
		int u = *s.begin();
		s.erase(*s.begin());
		top.push_back(u);
		for (auto j : liste[u]) {
			if (--grade[j] == 0) {
				s.insert(j);
			}
		}
	}

	for (auto i : top) {
		fout << i << " ";
	}
}
int main() {

	fin >> n >> m;
	while (m--) {
		int x, y;
		fin >> x >> y;
		liste[x].push_back(y);
	}

	top_sort();
}