Cod sursa(job #874705)

Utilizator gabriel93Robu Gabriel gabriel93 Data 9 februarie 2013 10:38:26
Problema Ciclu Eulerian Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.37 kb
#include<stdio.h>
#include<list>
#include<stack>
#define Nmax 100002
using namespace std;
int n,m;

list<int> g[Nmax];
stack<int> st;
int nr[Nmax];

void citire()
{
    int i,x,y;
    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);
        ++nr[x];
        ++nr[y];
    }
}

int check()
{
    int i;
    for(i=1;i<=n;++i)
        if(nr[i]&1)//daca este impar
        {
            return 0;
            break;
        }
    return 1;
}

void sterg(int x,int y)
{
    list<int>::iterator it;
    g[x].pop_front();
    for(it=g[y].begin();it!=g[y].end();++it)
        if(*it==x)
        {
            g[y].erase(it);
            break;
        }
}

void euler(int nod)
{
    int x;
    while(g[nod].empty()==0)
    {
        x=g[nod].front();
        st.push(nod);
        sterg(nod,x);
        nod=x;
    }
}

void rezolv()
{
    int ok,x;
    ok=check();
    if(ok==0)
    {
        printf("-1");
        return;
    }
    x=1;
    do
    {
        euler(x);
        x=st.top();
        st.pop();
        printf("%d ",x);
    }while(st.empty()==0);
}

int main()
{
    freopen("ciclueuler.in","r",stdin);
    freopen("ciclueuler.out","w",stdout);
    citire();
    rezolv();
    fclose(stdin);
    fclose(stdout);
    return 0;
}