Pagini recente » Rating Iulia Dinu (iulia_228) | Cod sursa (job #1551327) | Cod sursa (job #1048518) | Cod sursa (job #198477) | Cod sursa (job #2234183)
// 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;
}