Cod sursa(job #3159001)

Utilizator andu9andu nita andu9 Data 20 octombrie 2023 14:17:16
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.89 kb
#include <fstream>
#include <bitset>
#include <vector>
#include <algorithm>

std::ifstream fin("sortaret.in");
std::ofstream fout("sortaret.out");

const int nMax = 5e4 + 1;

std::bitset<nMax> vis;

std::vector<int> topSort;

std::vector<std::vector<int>> graph;

void dfs (int node) {
    vis[node] = true;
    for (int neighbour : graph[node])
        if (!vis[neighbour])
            dfs (neighbour);
    topSort.emplace_back (node);
}

int main () {
    int n, m; fin >> n >> m;
    graph.assign (n, std::vector<int> ());
    while (m > 0) {
        int x, y; fin >> x >> y;
        x -= 1, y -= 1;
        graph[x].emplace_back (y);
        m -= 1;
    }

    for (int i = 0; i < n; i += 1)
        if (!vis[i])
            dfs (i);

    std::reverse (topSort.begin (), topSort.end ());

    for (int i : topSort)
        fout << i + 1 << ' ';
    return 0;
}