Cod sursa(job #1416549)

Utilizator crucerucalinCalin-Cristian Cruceru crucerucalin Data 8 aprilie 2015 13:19:26
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.43 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <list>
#include <stack>

using Graph = std::vector<std::vector<int>>;

enum NODE_COLOR {
    WHITE,
    GRAY,
    BLACK
};

int dfs_fixed(int node,
              const Graph &G,
              std::vector<int> &nodes_state,
              std::stack<int> &result)
{
    nodes_state[node] = GRAY;
    for (auto &neigh : G[node])
        if ((nodes_state[neigh] == WHITE
             && dfs_fixed(neigh, G, nodes_state, result))
            || nodes_state[neigh] == GRAY)
            return 1;

    nodes_state[node] = BLACK;
    result.emplace(node);

    return 0;
}

std::stack<int> sort_topo(const Graph &G)
{
    std::stack<int> result;
    std::vector<int> visited(G.size(), WHITE);

    for (auto i = 0u; i < G.size(); ++i)
        if (visited[i] == WHITE && dfs_fixed(i, G, visited, result))
            return std::stack<int>{};

    return result;
}

int main()
{
    std::ifstream in{"sortaret.in"};
    std::ofstream out{"sortaret.out"};

    int N, M;
    in >> N >> M;

    Graph G(N);
    for (auto i = 0; i < M; ++i) {
        int x, y;
        in >> x >> y;

        G[x-1].emplace_back(y-1);
    }

    auto ordered = sort_topo(G);
    if (ordered.empty()) {
        std::cerr << "Graph has cycles" << std::endl;
        return 1;
    }

    while (!ordered.empty()) {
        auto vertex = ordered.top();
        ordered.pop();

        out << vertex + 1 << " ";
    }

    return 0;
}