Cod sursa(job #2704810)

Utilizator teofilotopeniTeofil teofilotopeni Data 11 februarie 2021 12:28:51
Problema Sortare topologica Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.87 kb
#include <stdio.h>
#include <vector>
#include <stack>
#include <bitset>
using namespace std;

//  Sortare topologica

vector<stack<int>> nodes;
bitset<50010> vizitat;
stack<int> coada;

void parcurge(int index) {
    vizitat[index] = true;
    for (; nodes[index].size(); nodes[index].pop())
        if (!vizitat[nodes[index].top()])
            parcurge(nodes[index].top());
    coada.push(index);
}

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<int>>(n + 1);
	while (m--) {
        scanf("%d %d", &x, &y);
        nodes[x].push(y);
        nodes[y].push(x);
	}
	for (int i = 1; i < (int)nodes.size(); i++)
        if (!vizitat[i])
            parcurge(i);

	for (; coada.size(); coada.pop())
        printf("%d ", coada.top());
	return 0;
}