Cod sursa(job #2898119)

Utilizator LIR16LazarIonutRadu LIR16 Data 6 mai 2022 00:56:00
Problema Sortare topologica Scor 60
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.86 kb
#include <iostream>
#include <stack>
#include <vector>
#define NMAX 50001
using namespace std;

stack<int> sts;
vector<int> adj[NMAX];
int viz[NMAX];
int n, m;

void DFS_TS(int node)
{
    viz[node] = 1;

    for (int i = 0; i < adj[node].size(); i++) {
        if (!viz[adj[node][i]])
            DFS_TS(adj[node][i]);
    }
    sts.push(node);
}

void Topological_Sort()
{
    for (int i = 1; i < n; i++) {
        if (!viz[i])
            DFS_TS(i);
    }

    while (!sts.empty()) {
        cout << sts.top() << " ";
        sts.pop();
    }
}

int main()
{
    freopen("sortaret.in", "r", stdin);
    freopen("sortaret.out", "w", stdout);
    cin >> n >> m;
    int node1, node2;
    for (int i = 1; i <= m; i++) {
        cin >> node1 >> node2;
        adj[node1].push_back(node2);
    }

    Topological_Sort();
    return 0;
}