Cod sursa(job #3148331)

Utilizator andreiomd1Onut Andrei andreiomd1 Data 31 august 2023 05:20:29
Problema Sortare topologica Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.88 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, m;
vector<int> G[NMAX];

bool used[NMAX];

vector<int> V;

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

    f >> n >> m;

    for (int i = 1; i <= m; ++i)
    {
        int x = 0, y = 0;
        f >> x >> y;

        G[x].push_back(y);
    }

    return;
}

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

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

    V.push_back(node);

    return;
}

int main()
{
    read();

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

    assert((int)V.size() == n);

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

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

    return 0;
}