Cod sursa(job #3235843)

Utilizator andreiomd1Onut Andrei andreiomd1 Data 22 iunie 2024 16:35:44
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.87 kb
#include <fstream>
#include <vector>

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 viz[nMAX];

vector<int> v = {};

static inline void read()
{
    f.tie(nullptr);
    f >> n;

    int m = 0;
    f >> m;

    int x = 0, y = 0;

    for (int i = 1; i <= m; ++i)
    {
        f >> x >> y,
            G[x].push_back(y);
    }

    return;
}

static void dfs(const int node)
{
    viz[node] = true;

    for (const int y : G[node])
        if (!viz[y])
            dfs(y);

    v.push_back(node);

    return;
}

int main()
{
    read();

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

    for (int i = (n - 1); i >= 0; --i)
    {
        g << v[i];

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

    return 0;
}