Cod sursa(job #3164995)

Utilizator andreiomd1Onut Andrei andreiomd1 Data 4 noiembrie 2023 22:32:19
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1 kb
#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;

ifstream f("sortaret.in");
ofstream g("sortaret.out");

static constexpr int NMAX = ((int)(5e4) + 1);

int n;
vector<int> G[NMAX];

bool Sel[NMAX];
vector<int> V = {};

static inline void load_graph()
{
    f.tie(nullptr);

    f >> n;

    int m = 0;
    f >> m;

    for (int q = 1; q <= m; ++q)
    {
        int u = 0, v = 0;
        f >> u >> v;

        G[u].push_back(v);
    }

    return;
}

static inline void dfs(const int &node)
{
    Sel[node] = 1;

    for (auto &it : G[node])
        if (!Sel[it])
            dfs(it);

    V.push_back(node);

    return;
}

static inline void topo_sort()
{
    for (int i = 1; i <= n; ++i)
        if (!Sel[i])
            dfs(i);

    reverse(V.begin(), V.end());

    return;
}

int main()
{
    load_graph();

    topo_sort();

    for (int i = 1; i <= n; ++i)
    {
        g << V[i - 1];

        if (i < n)
            g << ' ';
        else
            g << '\n';
    }

    return 0;
}