Cod sursa(job #3241182)

Utilizator not_anduAndu Scheusan not_andu Data 27 august 2024 14:43:40
Problema Ciclu Eulerian Scor 50
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.15 kb
#include <bits/stdc++.h>

using namespace std;

#define INFILE "ciclueuler.in"
#define OUTFILE "ciclueuler.out"

const int NODES_MAX = 1e5;

int nodes, edges;
vector<int> ans;
bool visited[NODES_MAX + 5];
vector<pair<int, int> > adj[NODES_MAX + 5];

void dfs(int node){
    while(!adj[node].empty()){
        pair<int, int> aux = adj[node].back();
        adj[node].pop_back();
        if(!visited[aux.second]){
            visited[aux.second] = true;
            dfs(aux.first);
        }
    }
    ans.push_back(node);
}

void solve(){

    cin >> nodes >> edges;
    for(int i = 0; i < edges; ++i){
        int node1, node2; cin >> node1 >> node2;
        adj[node1].push_back(make_pair(node2, i));
        adj[node2].push_back(make_pair(node1, i));
    }
    
    for(int i = 1; i <= nodes; ++i){
        if(adj[i].size() % 2 == 1) {
            cout << -1 << '\n';
            return;
        }
    }

    dfs(1);
    ans.pop_back();
    for(auto &it : ans){
        cout << it << " ";
    }

}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    freopen(INFILE, "r", stdin);
    freopen(OUTFILE, "w", stdout);
    solve();
    return 0;
}