Pagini recente » Cod sursa (job #3122970) | Borderou de evaluare (job #2673669) | Cod sursa (job #1039152) | Cod sursa (job #1833356) | Cod sursa (job #1705470)
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <utility>
#include <fstream>
#include <algorithm>
#include <vector>
#include <list>
#include <stack>
struct Node {
int id;
std::list<int> neighs;
int exit_time;
Node() : id(65535), exit_time(0) {}
};
int exittimeglob = 0;
bool sort_func (const Node &a, const Node &b) { return (a.exit_time > b.exit_time); }
void dfs(int N, int init_node, bool *visited, std::vector<Node> &graph) {
std::stack<int> S;
int curr_node;
S.push(init_node);
while(!S.empty()) {
curr_node = S.top(); S.pop();
if (!visited[curr_node]) {
visited[curr_node] = true;
for (std::list<int>::iterator neigh = graph[curr_node].neighs.begin();
neigh != graph[curr_node].neighs.end(); neigh++) {
if (!visited[*neigh]) { S.push(*neigh); };
}
}
graph[curr_node].exit_time = exittimeglob++;
}
}
int main(int argc, char **argv) {
std::ifstream input("sortaret.in");
std::ofstream output("sortaret.out");
int N, M, u, v;
if (!input.is_open() || !output.is_open()) {
std::cerr << "Cannot open input/output file!" << std::endl;
std::exit(-1);
}
// Citire Graph
input >> N >> M;
std::vector<Node> graph(N + 1);
while(input >> u >> v) {
graph[u].neighs.push_back(v);
graph[u].id = u;
graph[v].id = v;
}
bool visited[N + 1];
std::memset(visited, 0, N + 1);
// DFS
for (int i = 1; i <= N; i++)
if (!visited[i])
dfs(N, 1, visited, graph);
std::sort(graph.begin() + 1, graph.end(), sort_func);
for (int i = 1; i <= N; i++) output << graph[i].id << " ";
output << std::endl;
input.close();
output.close();
return 0;
}