Cod sursa(job #1452646)

Utilizator alex.bullzAlexandru Lilian alex.bullz Data 21 iunie 2015 15:57:49
Problema Sortare topologica Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.32 kb
#include <fstream>
#include <iostream>
#include <vector>

enum Color {
    WHITE,
    GRAY,
    BLACK
};

int g_time;

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[i].color == WHITE) {
            dfs (graph, i, fout);
        }
    }

    graph[index].color = BLACK;
    graph[index].finalizationTime = g_time;
    fout << index + 1<< " ";
    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 = 0; i < n; ++i) {
        if (graph[i].color == WHITE) {
            dfs (graph, i, fout);
        }
    }

    return 0;
}