Cod sursa(job #2549913)

Utilizator MichaelXcXCiuciulete Mihai MichaelXcX Data 18 februarie 2020 09:13:00
Problema Ciclu Eulerian Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.08 kb
#include <bits/stdc++.h>

using namespace std;

const char* input  = "ciclueuler.in";
const char* output = "ciclueuler.out";

const int NMAX = 100005, MMAX = 500005;

int N, M;
vector<pair<int, int>> G[NMAX];
vector<int> ans;
bool removed[MMAX];

void Euler(int x) {

    while(!G[x].empty()){
        int pos = G[x].back().second;
        int next = G[x].back().first;
        G[x].pop_back();
        if(!removed[pos]){
            removed[pos] = true;
            Euler(next);
        }
    }
    ans.push_back(x);
}

int main()
{
    ios_base::sync_with_stdio(NULL);
    cin.tie(NULL), cout.tie(NULL);

    freopen(input, "r", stdin);
    freopen(output, "w", stdout);

    cin >> N >> M;
    for(int i = 1; i <= M; ++i) {
        int x, y;
        cin >> x >> y;
        G[x].push_back({y, i});
        G[y].push_back({x, i});
    }

    for(int i = 1; i <= N; ++i)
        if(G[i].size() & 1) {
            cout << "-1\n";
            return 0;
        }

    Euler(1);

    for(int i = 0; i < ans.size() - 1; ++i)
        cout << ans[i] << " ";
}