Cod sursa(job #3266909)

Utilizator burcuriciBucur Stefan burcurici Data 10 ianuarie 2025 18:52:23
Problema Ciclu Eulerian Scor 80
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.24 kb
#include <bits/stdc++.h>
#include <fstream>
using namespace std;
ifstream fin("ciclueuler.in");
ofstream fout("ciclueuler.out");

struct much{
int x,y; bool viz=0;};

int n, m;
vector<much> M;
vector<vector<int>> a;
stack<int> st;
vector<int> sol;

void citire()
{
    fin>>n>>m;
    a.resize(n+1);
    for(int i=0; i<m; i++){
        int x,y;
        fin>>x>>y;
        much cur;
        cur.x=x; cur.y=y;
        M.push_back(cur);

        a[x].push_back(i);
        a[y].push_back(i);
    }
}

bool verif()
{
    for(auto it:a)
        if(it.size()%2==1)
            return 0;
    return 1;
}

void ex(int k)
{
    if(!a[k].empty()){
        for(vector<int>::reverse_iterator it=a[k].rbegin(); it<a[k].rend(); it++){
            if(M[*it].viz)
                a[k].pop_back();
            else{
                M[*it].viz=1;
                a[k].pop_back();
                if(M[*it].x==k)
                    ex(M[*it].y);
                else ex(M[*it].x);
            }
        }
        sol.push_back(k);
    }
}

int main()
{
    citire();
    if(!verif()) fout<<-1;
    else{
        ex(1);
        sol.pop_back();
        for(auto i:sol)
            fout<<i<<" ";
    }
    return 0;
}