Cod sursa(job #964050)

Utilizator marialivia16Chiorean Maria Livia marialivia16 Data 19 iunie 2013 23:25:42
Problema Ciclu Eulerian Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 1.2 kb
#include <iostream>
#include<vector>
#include<stack>
#define lim 100003
using namespace std;
int n,m,a,b;
vector<int> G[lim];
stack<int> st;

int paritate()
{
    for(int i=1;i<=n;i++)
        if(G[i].size()%2==0)
            return 0;
    return 1;
}
void sterge(int a,int b)
{
    vector<int>::iterator it;
    for(it=G[a].begin();it<G[a].end();it++)
    {
        if(*it==b)
        {
            G[a].erase(it);
            return;
        }
    }
}
void solutie()
{
    while(!st.empty())
    {
        int x=st.top();
        if(G[x].size()!=0)
        {
            int y=G[x].back();
            G[x].pop_back();
            sterge(y,x);
            st.push(y);
        }
        else
        {
            cout<<x<<" ";
            st.pop();
        }
    }
}
void citire()
{
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        cin>>a>>b;
        G[a].push_back(b);
        G[b].push_back(a);
    }
}
int main()
{
    freopen("ciclueuler.in","r",stdin);
    freopen("ciclueuler.out","w",stdout);
    citire();
    if(paritate()==0)
    {
        st.push(1);
        solutie();
    }
    else
    {
        cout<<"-1";
    }
    return 0;
}