Pagini recente » Cod sursa (job #1430546) | Cod sursa (job #1432395) | Cod sursa (job #1432645) | Cod sursa (job #1416549)
#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;
}