Cod sursa(job #2234183)

Utilizator skoda888Alexandru Robert skoda888 Data 25 august 2018 13:14:41
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.46 kb

// Arhiva Educationala - 004. Sortare Topologica

#include <iostream>
#include <fstream>
#include <list>
#include <vector>

enum Colour{
    BLACK,
    GREY,
    WHITE
};

std::vector<long> t_sorted_edges;

void DFS(std::list<long> adj_list[], long vertex, Colour colour[])
{
    colour[vertex] = GREY;

    for(std::list<long>::iterator it = adj_list[vertex].begin(); it != adj_list[vertex].end(); ++it){
        if(colour[*it] == WHITE){
            DFS(adj_list, *it, colour);
        }
    }


    t_sorted_edges.push_back(vertex);
    colour[vertex] = BLACK;
}

void sortare_topologica(std::list<long> adj_list[], long _N, Colour colour[])
{
    for(int i = 1; i <= _N; ++i){
        if(colour[i] == WHITE){
            DFS(adj_list, i, colour);
        }
    }
}

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

    long N;
    long M;
    in >> N >> M;

    std::list<long> adj_list[N + 1];
    for(int i = 1; i <= M; ++i){
        long vertex_1;
        long vertex_2;
        in >> vertex_1 >> vertex_2;
        adj_list[vertex_1].push_back(vertex_2);
    }

    Colour colour[N + 1] = {};

    for(int i = 1; i <= N; ++i){
        colour[i] = WHITE;
    }
    sortare_topologica(adj_list, N, colour);

    for(std::reverse_iterator<std::vector<long>::iterator> it = t_sorted_edges.rbegin(); it != t_sorted_edges.rend(); ++it){
        out << *it << ' ';
    }
    return 0;
}