Cod sursa(job #2708801)

Utilizator teofilotopeniTeofil teofilotopeni Data 19 februarie 2021 14:09:28
Problema Sortare topologica Scor 80
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.84 kb
#include <iostream>
#include <vector>
#include <stack>
using namespace std;

//  Sortare topologica

vector<stack<short>> nodes;
short parents[50010];

void parcurge(short index) {
    parents[index]--;
    if (!parents[index]) {
        cout << index << ' ';
        parents[index]--;

        while (nodes[index].size()) {
            parcurge(nodes[index].top());
            nodes[index].pop();
        }
    }
}

int main() {
	freopen("sortaret.in", "r", stdin);
	freopen("sortaret.out", "w", stdout);
	int n, m, x, y;
	scanf("%d %d", &n, &m);
	nodes = vector<stack<short>>(n + 1);
	while (m--) {
        scanf("%d %d", &x, &y);
        nodes[x].push(y);
        parents[y]++;
	}
	for (x = 1; x <= n; x++) {
        if (!parents[x]) {
            parents[x]++;
            parcurge(x);
        }
	}
	return 0;
}