Cod sursa(job #2565790)

Utilizator SqueekDanielTodasca Daniel SqueekDaniel Data 2 martie 2020 16:49:34
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.81 kb
#include <bits/stdc++.h>

#define MAXN    50005

#define FILENAME    std::string("sortaret")
std::ifstream input (FILENAME+".in");
std::ofstream output(FILENAME+".out");

int N, M;
std::vector <int> ADC[MAXN];
inline void addEdge(int u, int v) {
    ADC[u].push_back(v);
}

bool seen[MAXN];
std::vector <int> topsort;
void DFS(int vertex = 1) {
    seen[vertex] = vertex;
    for (auto &it:ADC[vertex]) {
        if (seen[it]) continue;
        DFS(it);
    }   topsort.push_back(vertex);
}
void topSort() {
    for (int i=1; i<=N; ++i)
        if (!seen[i]) DFS(i);
}

int main()
{
    input >> N >> M;
    for (int i=0, u, v; i<M; ++i)
        input >> u >> v, addEdge(u, v);
    topSort();
    for (int i=topsort.size()-1; i>=0; --i)
        output << topsort[i] << ' ';

    return 0;
}