Cod sursa(job #2198873)

Utilizator AvramDanielAvram Daniel AvramDaniel Data 25 aprilie 2018 18:25:34
Problema Ciclu Eulerian Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 1.03 kb
#include <bits/stdc++.h>
using namespace std;

int n,m,a,b;
vector <int> v[100010];
vector<int> d;
void euler(int nod)
{
    d.push_back(nod);
    while(v[nod].size())
    {
        int ap,i=0;
        while((v[v[nod][i]].size())<2 && i<v[nod].size()-1) i++;
        ap=v[nod][i];
       // cout<<v[nod][i];
        v[nod].erase(v[nod].begin()+i);
        i=0;
        while(v[ap][i]!=nod)
        {
            i++;
        }
        v[ap].erase(v[ap].begin()+i);
        euler(ap);
    }
}

int main ()
{
    ifstream cin("ciclueuler.in");
    ofstream cout("ciclueuler.out");
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        cin>>a>>b;
        v[a].push_back(b);
        //if(a!=b)
        v[b].push_back(a);
    }
    bool u=1;
    for(int i=1;i<=n && u;i++)
        if (v[i].size()%2) u=0;
    if(u)
    {
        euler(1);
        if(d[d.size()-1]==1)
        for(int i=0;i<d.size()-1;i++)
            cout<<d[i]<<' ';
        else cout<<"-1";
    }
    else cout<<"-1";
    return 0;
}