Cod sursa(job #2916730)

Utilizator andreiomd1Onut Andrei andreiomd1 Data 31 iulie 2022 20:17:49
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.2 kb
#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;

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

const int NMAX = 5e4 + 1;

int N;
bool used[NMAX];

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

vector < int > List;

static inline void Add_Edge (int u, int v)
{
    G[u].push_back(v);

    return;
}

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

    f >> N;

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

        Add_Edge(x, y);
    }

    return;
}

static inline void DFS (int Node)
{
    used[Node] = 1;

    for(auto it : G[Node])
        if(!used[it])
            DFS(it);

    List.push_back(Node);

    return;
}

static inline void Topo_Sort ()
{
    for(int i = 1; i <= N; ++i)
        if(!used[i])
            DFS(i);

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

    return;
}

static inline void Write ()
{
    for(int i = 1; i <= N; ++i)
    {
        g << List[i - 1];

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

    return;
}

int main()
{
    Read();

    Topo_Sort();

    Write();

    return 0;
}