Cod sursa(job #3195330)

Utilizator dobreraduDobre Radu Fabian dobreradu Data 20 ianuarie 2024 14:39:07
Problema Ciclu Eulerian Scor 80
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.25 kb
#include <bits/stdc++.h>

using namespace std;
ifstream in("ciclueuler.in");
ofstream out("ciclueuler.out");
const int NMAX = 1e5+5;
const int MMAX = 5e5+5;
int n, m;
struct Edge{
    int node1, node2;
};
vector <Edge> edges;
vector <int> euler;
vector <int> g[NMAX];
bool deleted[MMAX];

int get_next( int node ){
    while( !g[node].empty() && deleted[g[node].back()] )
        g[node].pop_back();
    if( g[node].empty() )
        return 0;
    int edge_idx = g[node].back();
    deleted[edge_idx] = true;
    Edge edge = edges[edge_idx];
    return edge.node1 + edge.node2 - node;
}

void find_euler( int node ){
    while( int nxt = get_next(node) )
        find_euler(nxt);
    euler.push_back(node);
}
int main()
{
    in >> n >> m;
    for( int i = 1; i <= m; i++) {
        Edge curr_edge;
        in >> curr_edge.node1 >> curr_edge.node2;
        edges.push_back(curr_edge);
        g[curr_edge.node1].push_back(edges.size()-1);
        g[curr_edge.node2].push_back(edges.size()-1);
    }
    find_euler(1);
    for( int i = 1; i <= n; i++ )
        if( g[i].size() % 2 ){
            out << -1;
            return 0;
        }
    for( int i = 0; i < euler.size()-1; i++ )
        out << euler[i] << " ";
    return 0;
}