Cod sursa(job #1452675)

Utilizator alex.bullzAlexandru Lilian alex.bullz Data 21 iunie 2015 16:45:02
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.46 kb
#include <fstream>
#include <iostream>
#include <vector>
#include <queue>
#include <stack>

enum Color {
    WHITE,
    GRAY,
    BLACK
};

int g_time;
std::stack<int> q;

struct Node {
    int index;
    int discoveryTime;
    Color color;
    int finalizationTime;
    std::vector<int> neighbours;

    Node() {
        discoveryTime = -1;
        color = WHITE;
        finalizationTime = -1;
    }
};

void dfs (std::vector<Node> &graph, int index, std::ofstream &fout) {
    graph[index].discoveryTime = g_time;
    g_time++;
    graph[index].color = GRAY;

    auto neighs = graph[index].neighbours;
    for (int i = 0; i < neighs.size(); ++i) {
        if (graph[neighs[i]].color == WHITE) {
            dfs (graph, neighs[i], fout);
        }
    }

    graph[index].color = BLACK;
    graph[index].finalizationTime = g_time;
    q.push (index);
    g_time++;
}

int main() {
    std::ifstream fin ("sortaret.in");
    std::ofstream fout ("sortaret.out");
    int n, m, source, dest;

    fin >> n >> m;
    std::vector<Node> graph (n+1);

    for (int i = 0; i < m; ++i) {
        fin >> source >> dest;
        graph[source].neighbours.push_back (dest);
//        std::cout << "(" << source << ", " << dest << ")\n";
    }
//    std::cout << "terminat citit!!!\n";
    for (int i = 1; i <= n; ++i) {
        if (graph[i].color == WHITE) {
            dfs (graph, i, fout);
        }
    }

    while (!q.empty()) {
        fout << q.top() << " ";
        q.pop();
    }

    return 0;
}