Cod sursa(job #1802913)

Utilizator adystar00Bunea Andrei adystar00 Data 10 noiembrie 2016 19:38:09
Problema Ciclu Eulerian Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.59 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
ifstream fin ("ciclueuler.in");
ofstream fout ("ciclueuler.out");
struct prb
{
    int nod,mu;
};
vector <prb> g[100010];
int n,k,st[500010],vc[500010],viz[500010];;
void citire ()
{
    int m,i,a,b;
    prb val;
    fin>>n>>m;
    for(i=1; i<=m; i++)
    {
        fin>>a>>b;
        val.nod=b;
        val.mu=i;
        viz[a]++;
        viz[b]++;
        g[a].push_back(val);
        val.nod=a;
        g[b].push_back(val);
    }
}
void parcurgere(int x)
{
    int i,pp,a=g[x].size(),fiu;
    while(a!=0)
    {
        while(a>0&&vc[g[x].back().mu]==1)
        {
            g[x].pop_back();
            a--;
        }
        //cout<<x<<" "<<"\n";
        if(a>0)
        {
            fiu=g[x].back().nod;
            //cout<<x<<" "<<fiu<<"\n";
            vc[g[x].back().mu]=1;
            k++;
            st[k]=fiu;
            g[x].pop_back();
            x=fiu;
            a=g[x].size();
        }
        //cout<<k<<"\n";
    }
}
int main()
{
    int i,j,nd,pp=0;
    citire();
    /*for(i=1;i<=n;i++){
        for(j=0;j<g[i].size();j++)
            fout<<g[i][j].nod<<" ";
        fout<<"\n";
    }*/
    for(i=1; i<=n; i++)
        if(viz[i]%2==1)
            pp=1;
    if(pp==1)
        fout<<"-1";
    else
    {
        st[1]=1;
        k=1;
        while(k!=0)
        {
            nd=st[k];
            parcurgere(nd);
            if(k>1)
                fout<<st[k]<<" ";
            k--;
        }
    }
    return 0;
}