Cod sursa(job #3313708)

Utilizator iulia_morariuIuli Morariu iulia_morariu Data 5 octombrie 2025 22:41:26
Problema Ciclu Eulerian Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.53 kb
#include <algorithm>
#include <iostream>
#include <fstream>
#include <climits>
#include <vector>
#include <stack>
#include <cmath>
#include <set>
// #include <bits/stdc++.h>
#define in  fin
#define out fout
#define mkp make_pair

using namespace std;

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

// lowkey nu am somn sooo in loc sa vegetez ma apuc de tema

vector< pair<int, int> > g[100001];
pair<int, int> mch[500001];
int it[100001];

// mi-am amintit de ce optimizari am discutat la prega

bool alr_bro[500001]; // puse deja
vector<int> finally;

void euler_died_for_this(int nod){
    while(it[nod] < g[nod].size()){
        int x = g[nod][ it[nod] ].first;
        int dar_cine_tea_intrebat = g[nod][ it[nod] ].second;
        it[nod]++;

        if(!alr_bro[ dar_cine_tea_intrebat ]){
            alr_bro[ dar_cine_tea_intrebat ] = 1;
            euler_died_for_this(x);
        }
    }
    finally.push_back(nod);
}

signed main(){
    ios_base::sync_with_stdio(false);
    in.tie(NULL);

    int n, m; in >> n >> m;
    for(int i = 0; i < m; i++){
        int x, y; in >> x >> y;
        g[x].push_back( mkp(y, i) );
        g[y].push_back( mkp(x, i) );

        mch[i] = mkp(x, y);
    }
    
    bool pudak = 0;
    for(int i = 1; i <= n; i++){
        if(g[i].size() % 2 == 1) pudak = 1;
    }
    if(pudak) out << "-1\n";
    else{
        euler_died_for_this(1);
        finally.pop_back(); // nu am nevoie de 1
        if(finally.size() != m) out << "-1\n";
        for(const int &x : finally) out << x << " ";
    }

    return 0;
}