Pagini recente » Cod sursa (job #2592987) | Cod sursa (job #439368) | Monitorul de evaluare | Cod sursa (job #952818) | Cod sursa (job #3327147)
// https://www.infoarena.ro/problema/ciclueuler
#include <fstream>
#include <cstring>
#include <vector>
std::ifstream in("ciclueuler.in");
std::ofstream out("ciclueuler.out");
struct edge_t {
unsigned node;
unsigned id;
};
struct node_t {
std::vector<edge_t> conections;
};
void ciclueuler(
node_t const* const graph,
bool* const found_edge,
std::vector<unsigned>& node_path,
unsigned node
) {
for(edge_t const& edge : graph[node].conections) {
if(found_edge[edge.id]) continue;
found_edge[edge.id] = true;
ciclueuler(graph, found_edge, node_path, edge.node);
}
node_path.push_back(node);
}
int main() {
unsigned nodes, edges;
in >> nodes >> edges;
node_t graph[100001];
for(unsigned a, b, edge = 0; edge < edges; edge += 1) {
graph[a].conections.push_back (
edge_t {
.node = b,
.id = edge
}
);
graph[b].conections.push_back (
edge_t {
.node = a,
.id = edge
}
);
}
for(unsigned node = 0; node < nodes; node += 1) {
if(graph[node].conections.size() % 2 != 0) {
out << "-1";
return 0;
}
}
bool found_edge[500000];
std::memset(found_edge, 0x00, 500000);
std::vector<unsigned> node_path;
ciclueuler(graph, found_edge, node_path, 0);
for(unsigned edge = 0; edge < edges; edge += 1) {
if(found_edge[edge]) continue;
out << "-1";
return 0;
}
for(unsigned const& node : node_path) {
out << node << ' ';
}
}