Cod sursa(job #1817539)

Utilizator vladbatalanBatalan Vlad vladbatalan Data 27 noiembrie 2016 23:53:10
Problema Ciclu Eulerian Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 1.33 kb
#include <fstream>
#include <iostream>
#include <bitset>
#include <algorithm>
#include <vector>
#define NX 100010
#define pb push_back

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

int n,m,x,y,nr_viz;
int deg[NX+1];
bitset<NX> viz;
vector<int> v[NX+1],A;

void del(int a,int b)
{
    vector<int>::iterator g;
    g=find(v[a].begin(),v[a].end(),b);
    v[a].erase(g);
    g=find(v[b].begin(),v[b].end(),a);
    v[b].erase(g);
}

void euler(int p)
{
    int w;
    while(!v[p].empty())
    {
        w=v[p].back();
        v[p].pop_back();
        for(auto it=v[w].begin(); it!=v[w].end(); it++)
            if(*it==p)
            {
                v[w].erase(it);
                break;
            }
        euler(w);
    }
    if(!viz[p])
    {
        nr_viz++;
        viz[p]=1;
    }
    A.pb(p);
}
int main()
{
    fin>>n>>m;
    while(m--)
    {
        fin>>x>>y;
        v[x].pb(y);
        v[y].pb(x);
        deg[x]++;
        deg[y]++;
    }
    for(int i=1; i<=n; i++)
        if(deg[i]%2!=0)
        {
            fout<<-1;
            return 0;
        }
    nr_viz=0;
    euler(1);
    if(nr_viz!=n)
    {
        fout<<-1;
        return 0;
    }
    A.pop_back();
    for(auto it:A)
        fout<<it<<' ';
    return 0;
}