Cod sursa(job #2352720)

Utilizator SqueekDanielTodasca Daniel SqueekDaniel Data 23 februarie 2019 17:10:56
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.77 kb
#include <bits/stdc++.h>

#define MAXN 50005

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

inline void AddEdge(int X, int Y) {
    ADC[X].push_back(Y);
}

bool Seen[MAXN];
void DFS(int Vertex) {
    Seen[Vertex] = 1;
    for (auto Edge:ADC[Vertex])
        if (!Seen[Edge])
            DFS(Edge);
    FinishList.push_back(Vertex);
}

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

void Citire() {
    In >> N >> M;
    for (int i=1, 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=N-1; i>=0; --i, Out << ' ')
        Out << FinishList[i];
}

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

    return 0;
}