Cod sursa(job #2272278)

Utilizator SqueekDanielTodasca Daniel SqueekDaniel Data 29 octombrie 2018 22:11:46
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.27 kb
#include <bits/stdc++.h>

#define MaxN 50005
#define inf  (int)(1e9)

std::ifstream InFile("sortaret.in");
std::ofstream OutFile("sortaret.out");

int M;

template <int NNodes> class UndirectedGraph {
public:
    int N;

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

    void Sort() {
        for (int i=0; i<N; ++i)
            if (!Seen[i+1])
                DFS(i+1);
    }

    void Print() {
        for (int i=N-1; i>=0; --i)
            OutFile << Perm[i] << ' ' ;
    }

private:
    std::vector <int> Perm;             // Ordinea varfurilor dupa sortare (dar o realizam descrescator pt ca vector STL)

    struct NodeData {
        std::list <int> ADC;
    }   Node[MaxN];

    bool Seen[NNodes];
    void DFS(int Vertex) {
        Seen[Vertex] = 1;

        for (auto Vecin:Node[Vertex].ADC)
            if (!Seen[Vecin])
                DFS(Vecin);
        Perm.push_back(Vertex);
    }

};  UndirectedGraph <MaxN> Graph;

void Citire() {
    InFile >> Graph.N >> M;

    for (int i=0, x, y, dist; i<M; ++i)
        InFile >> x >> y,
        Graph.AddEdge(x, y);
}

void Rezolvare() {
    Graph.Sort();
    Graph.Print();
}

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

    return 0;
}