Cod sursa(job #1256564)

Utilizator Alexa2001Alexa Tudose Alexa2001 Data 6 noiembrie 2014 16:03:49
Problema Ciclu Eulerian Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.06 kb
#include <cstdio>
#include <vector>
#include <stack>
#include <algorithm>

using namespace std;

vector<int> G[100009],sol;
stack<int> st;
int i,n,m,x,y;

inline void euler(int x)
{
    st.push(x);
    int nod,last;

    while(!st.empty())
    {
       nod=st.top();

       if(G[nod].size())
       {
           last=G[nod].back();
           G[nod].pop_back();
           st.push(last);
           G[last].erase( find( G[last].begin(),G[last].end(),nod ) );

       }
       else
       {
           sol.push_back(nod);
           st.pop();

       }

    }


}


int main()
{
    freopen("ciclueuler.in","r",stdin);
    freopen("ciclueuler.out","w",stdout);

    scanf("%d%d",&n,&m);

    for(i=1;i<=m;++i)
    {
        scanf("%d%d",&x,&y);
        G[x].push_back(y);
        G[y].push_back(x);

    }

    for(i=1;i<=n;++i)
    if(G[i].size()&1)
    {
        printf("-1\n");
        return 0;
    }


    euler(1);

    for(i=0;i<(int)sol.size()-1;++i)
    printf("%d ",sol[i]);





    return 0;
}