Cod sursa(job #2696703)

Utilizator Andrei012Trache Andrei Andrei012 Data 16 ianuarie 2021 13:37:49
Problema Ciclu Eulerian Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.02 kb
#include <bits/stdc++.h>

using namespace std;

vector<int> v[100002];
vector<int> sol;
int a[500002],b[500002],parc[500001],grad[100001],ans[500001];
int muchie;
void euler(int nod1){
    while(v[nod1].size()!=0){
        muchie=v[nod1].back();
        v[nod1].pop_back();
        if(parc[muchie]==1)
            continue;
        parc[muchie]=1;
        int vecin=(nod1^a[muchie]^b[muchie]);
        euler(vecin);
    }
    sol.push_back(nod1);
}


int main()
{
    ifstream cin("ciclueuler.in");
    ofstream cout("ciclueuler.out");

    int n,m,i,j=0;
    cin>>n>>m;
    for(i=1;i<=m;++i){
        cin>>a[i]>>b[i];
        ++grad[a[i]];
        ++grad[b[i]];
        v[a[i]].push_back(i);
        v[b[i]].push_back(i);
    }
    for(i=1;i<=n;++i)
        if(grad[i]%2)
        {
            cout<<-1;
            return 0;
        }
    euler(1);
    while(sol.size()!=0){
        ans[++j]=sol.back();
        sol.pop_back();
    }
    while(j>1)
        cout<<ans[j--]<<" ";
    return 0;
}