Cod sursa(job #1277492)

Utilizator alex_bucevschiBucevschi Alexandru alex_bucevschi Data 27 noiembrie 2014 19:17:54
Problema Ciclu Eulerian Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 1.23 kb
#include <bits/stdc++.h>
#define N 100010
#define pb push_back
using namespace std;
ifstream fin("ciclueuler.in");
ofstream fout("ciclueuler.out");
int viz[N],n,m,i,x,y;
vector<int>v[N],st;
void df(int nod)
{
    viz[nod]=1;
    for(auto vec:v[nod])
        if(!viz[vec])
            df(vec);
}
int main()
{
    fin>>n>>m;
    for(;m;m--)
    {
        fin>>x>>y;
        v[x].pb(y);
        v[y].pb(x);
    }
    for(i=1;i<=n;i++)
        if(v[i].size()&1)
        {
            cout<<-1<<'\n';
            return 0;
        }
    df(1);
    for(i=1;i<=n;i++)
        if(!viz[i])
        {
            cout<<-1<<'\n';
            return 0;
        }
    st.pb(1);
    while(st.size())
    {
        x=st.back();
        if(v[x].size())
        {
            y=v[x].back();
            v[x].pop_back();
            for(vector<int>::iterator vec=v[y].begin();vec!=v[y].end();vec++)
                if(*vec==x)
                {
                    *vec=v[y].back();
                    v[y].pop_back();
                    break;
                }
            st.pb(y);
        }
        else
        {
            fout<<st.back()<<' ';
            st.pop_back();
        }
    }
    return 0;
}