Cod sursa(job #2298304)

Utilizator SqueekDanielTodasca Daniel SqueekDaniel Data 7 decembrie 2018 22:58:08
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.77 kb
#include <bits/stdc++.h>

#define MAXN 500005

int N, M;
std::vector <int> ADC[MAXN];

inline void AddEdge(int x, int y) {
    ADC[x].push_back(y);
}

bool Seen[MAXN];
std::vector <int> VTop;

void DFS(int Vertex) {
    Seen[Vertex] = 1;
    for (auto Vecin:ADC[Vertex])
        if (!Seen[Vecin])
            DFS(Vecin);
    VTop.push_back(Vertex);
}

std::ifstream In("sortaret.in");
std::ofstream Out("sortaret.out");

void Citire() {
    In >> N >> M;
    for (int i=0, x, y; i<M; ++i)
        In >> x >> y, AddEdge(x, y);
}

void Rezolvare() {
    for (int i=1; i<=N; ++i)
        if (!Seen[i])
            DFS(i);
    for (int i=0; i<N; ++i)
        Out << VTop[N-i-1] << ' ';
}

int main()
{
    Citire();
    Rezolvare();

    return 0;
}