Cod sursa(job #1845863)

Utilizator NineshadowCarapcea Antonio Nineshadow Data 11 ianuarie 2017 22:25:00
Problema Ciclu Eulerian Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.03 kb
#include <bits/stdc++.h>
#define MAXN 100001
#define MAXM 500001
using namespace std;
ifstream in("ciclueuler.in");
ofstream out("ciclueuler.out");
int n,m;
list<int> v[MAXN], ans;
void euler_cycle()
{
    stack<int> stk;
    stk.push(1);
    unsigned nod=1;
    do
    {
        while(!v[nod].empty())
        {
            unsigned w=*v[nod].begin();
            stk.push(nod);
            v[w].erase(find(v[w].begin(),v[w].end(),nod));
            v[nod].erase(v[nod].begin());
            nod=w;
        }
        nod=stk.top();
        ans.push_back(nod);
        stk.pop();
    }while(!stk.empty());
}
int main()
{
    in>>n>>m;
    for(int i=1; i<=m; ++i)
    {
        int x,y;
        in>>x>>y;
        v[x].push_back(y);
        v[y].push_back(x);
    }
    for(int i=1; i<=n; ++i)
        if(v[i].size() & 1)
        {
            out<<-1;
            return 0;
        }
    euler_cycle();
    ans.pop_back();
    for(auto i=ans.begin();i!=ans.end();++i)
        out<<*i<<' ';
    return 0;
}