Cod sursa(job #2399782)

Utilizator sMateiMatei Scoica sMatei Data 7 aprilie 2019 23:53:37
Problema Ciclu Eulerian Scor 0
Compilator cpp-32 Status done
Runda Arhiva educationala Marime 1.12 kb
#include <fstream>

#include <vector>

#include <stack>



using namespace std;

ifstream in("ciclueuler.in");

ofstream out("ciclueuler.out");

const int N=100005;

vector<int>v[N],sol;

int n,m,vx[5*N],vy[5*N];

bool used[5*N];

stack<int>st;



int main()

{

    in>>n>>m;

    for(int i=1,x,y;i<=m;i++)

    {

        in>>x>>y;

        v[x].push_back(i);

        v[y].push_back(i);

        vx[i]=x;

        vy[i]=y;

    }

    for(int i=1;i<=n;i++)

        if(v[i].size()%2!=0)

        {

            out<<-1;

            return 0;

        }

    st.push(1);

    int vf,e,next;

    while(!st.empty())

    {

        vf=st.top();

        if(v[vf].size()==0)

        {

            st.pop();

            sol.push_back(vf);

            continue;

        }

        e=v[vf].back();

        v[vf].pop_back();

        if(!used[e])

        {

            used[e]=true;

            next=vy[e];

            st.push(next);

        }

    }

    for(unsigned i=0;i<sol.size();i++)

        out<<sol[i]<<' ';

    return 0;

}