Cod sursa(job #2668871)

Utilizator Alex_tz307Lorintz Alexandru Alex_tz307 Data 5 noiembrie 2020 17:03:53
Problema Ciclu Eulerian Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.91 kb
#include <bits/stdc++.h>

using namespace std;

ifstream fin("ciclueuler.in");
ofstream fout("ciclueuler.out");

vector < vector < pair < int , int > > > G;
vector < bool > viz;
vector < int > sol;

void DFS(int node) {
    while(!G[node].empty()) {
        auto vec = G[node].back();
        G[node].pop_back();
        if(!viz[vec.second]) {
            viz[vec.second] = true;
            DFS(vec.first);
        }
    }
    sol.emplace_back(node);
}

int main() {
    int N, M;
    fin >> N >> M;
    G.resize(N + 1);
    viz.resize(M);
    for(int i = 0; i < M; ++i) {
        int u, v;
        fin >> u >> v;
        G[u].emplace_back(v, i);
        G[v].emplace_back(u, i);
    }
    for(int i = 1; i <= N; ++i)
        if(G[i].size() & 1) {
            fout << -1;
            return 0;
        }
    DFS(1);
    sol.pop_back();
    for(int node : sol)
        fout << node << ' ';
}