Cod sursa(job #3140301)

Utilizator andreiomd1Onut Andrei andreiomd1 Data 5 iulie 2023 14:30:29
Problema Sortare topologica Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.93 kb
#include <fstream>
#include <vector>
#include <cassert>

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 Read()
{
    f.tie(nullptr);

    f >> n;

    int m = 0;
    f >> m;

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

        G[x].push_back(y);
    }

    return;
}

static inline void DFS(int node)
{
    Sel[node] = 1;

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

    V.push_back(node);
}

int main()
{
    Read();

    for (int i = 1; i <= n; ++i)
        if (!Sel[i])
            DFS(i);

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

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

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

        if (i != (n - 1))
            g << ' ';
        else
            g << '\n';
    }

    return 0;
}