Cod sursa(job #3327147)

Utilizator g.vladGociu Vlad g.vlad Data 2 decembrie 2025 16:28:58
Problema Ciclu Eulerian Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.7 kb

// 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 << ' ';
    }
}