Pagini recente » Cod sursa (job #1246977) | Cod sursa (job #570626) | Cod sursa (job #1927123) | Cod sursa (job #255386) | Cod sursa (job #2149800)
#include <fstream>
#include <list>
#include <vector>
enum COLOR
{
WHITE, GREY, BLACK
};
std::vector<COLOR> color;
std::list<int> sortedNodes;
class Graph {
int V;
std::list<int> *adj;
void explore(int node);
public:
Graph(int V);
void addUndirectedEdge(int u, int v);
void addDirectedEdge(int s, int d);
/* Topological Sort */
void TopologicalSort();
};
Graph::Graph(int V) {
this->V = V;
adj = new std::list<int>[V];
}
void Graph::addUndirectedEdge(int u, int v) {
adj[u].push_back(v);
adj[v].push_back(u);
}
void Graph::addDirectedEdge(int s, int d) {
adj[s].push_back(d);
}
void Graph::TopologicalSort() {
for (int i = 0; i < V; i++) {
if (color[i] == WHITE) {
explore(i);
}
}
}
void Graph::explore(int node) {
color[node] = GREY;
for (auto it = adj[node].begin(); it != adj[node].end(); it++) {
if (color[*it] == WHITE) {
color[*it] = GREY;
explore(*it);
}
}
color[node] = BLACK;
sortedNodes.push_front(node + 1);
}
void printSolution() {
std::ofstream fout("sortaret.out");
for (auto it = sortedNodes.begin(); it != sortedNodes.end(); it++)
fout << *it << " ";
}
int main(void) {
int N, M, s, d;
std::ifstream fin("sortaret.in");
fin >> N >> M;
Graph graph = Graph(N);
color.resize(N, WHITE);
for (int i = 0; i < M; i++) {
fin >> s >> d;
graph.addDirectedEdge(s - 1, d - 1);
}
graph.TopologicalSort();
printSolution();
return 0;
}