Cod sursa(job #1870667)

Utilizator caprariuapCaprariu Alin-Paul caprariuap Data 6 februarie 2017 20:23:58
Problema Ciclu Eulerian Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 1.22 kb
#include <iostream>
#include <cstdio>
#include <vector>

using namespace std;

vector <int> v[100010];
int n,m,i,j,vf,st[100010],ans[100010];

int main()
{
    freopen("ciclueuler.in","r",stdin);
    freopen("ciclueuler.out","w",stdout);
    cin>>n>>m;
    for (i=1; i<=m; i++)
    {
        int a,b;
        cin>>a>>b;
        v[a].push_back(b);
        v[b].push_back(a);
    }
    for (i=1; i<=n; i++)
        if (v[i].size()%2!=0||v[i].size()==0)
        {
            cout << "-1\n";
            return 0;
        }
    int x,nr=0;
    vf=-1;
    st[++vf]=1;
    while (vf>=0)
    {
        bool ok=0;
        x=st[vf];
        if (v[x].size()>0)
        {
            int y=v[x][v[x].size()-1];
            v[x].pop_back();
            int gasit=0;
            for (int j=0; j<v[y].size()&&!gasit; j++)
                if (v[y][j]==x)
                {
                    swap(v[y][j],v[y][v[y].size()-1]);
                    v[y].pop_back();
                    gasit=1;
                }
            st[++vf]=y;
            ok=1;
        }
        if (!ok)
        {
            vf--;
            ans[++nr]=x;
        }
    }
    for (i=1; i<nr; i++)
        cout << ans[i] << ' ';
}