Cod sursa(job #3206328)

Utilizator AlexRzvAlex Razvan AlexRzv Data 22 februarie 2024 12:21:20
Problema Ciclu Eulerian Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.12 kb
#include <bits/stdc++.h>
using namespace std;

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

const int NMAX = 1e5;

int n,m;
vector < pair < int, int > > G[NMAX + 1];
int grad[NMAX + 1];
stack < int > rez, s;
bool viz[ 5 * NMAX + 1];

void euler(int nod){
    s.push(nod);
    while(!s.empty()){
        int nodc = s.top();
        if(G[nodc].size()){
            auto [nod_nbr, ind_muc] = G[nodc].back();
            G[nodc].pop_back();
            if(!viz[ind_muc]){
                viz[ind_muc] = true;
                s.push(nod_nbr);
            }
        }
        else{
            s.pop();
            rez.push(nodc);
        }
    }
}

int main(){

    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});
        grad[x]++;
        grad[y]++;
    }
    for(int i = 1;i<=n;++i)
        if(grad[i] % 2){
            cout << -1;
            return 0;
        }
    euler(1);
    while(!rez.empty()){
        cout << rez.top() << ' ';
        rez.pop();
    }
    return 0;
}