Cod sursa(job #1404458)

Utilizator alex_unixPetenchea Alexandru alex_unix Data 28 martie 2015 11:21:58
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.95 kb
#include <fstream>
#include <vector>
#include <stack>

const int MAX_N(50001);

int n, m;
bool Mark [MAX_N];
std::vector<int> Graph [MAX_N];
std::stack<int> Stack;

inline void Read (void)
{
    std::ifstream input("sortaret.in");
    input >> n >> m;
    int x, y;
    while (m)
    {
        input >> x >> y;
        Graph[x].push_back(y);
        --m;
    }
    input.close();
}

inline void Print (void)
{
    std::ofstream output("sortaret.out");
    while (!Stack.empty())
    {
        output << Stack.top() << ' ';
        Stack.pop();
    }
    output.close();
}

void Toposort (int node)
{
    Mark[node] = true;
    for (unsigned int i(0) ; i < Graph[node].size() ; ++i)
        if(!Mark[Graph[node][i]])
            Toposort(Graph[node][i]);
    Stack.push(node);
}

int main (void)
{
    Read();
    for (int i(1) ; i <= n ; ++i)
        if (!Mark[i])
            Toposort(i);
    Print();
    return 0;
}