Cod sursa(job #875309)

Utilizator tudgal1001Profir Tudor tudgal1001 Data 9 februarie 2013 21:47:05
Problema Ciclu Eulerian Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 1.26 kb
#include<cstdio>
#include<stack>
#include<list>
#define NMax 100005
using namespace std;

int sol[NMax],n,k;
list <int> v[NMax];
list <int>::iterator it;
stack <int> s;

int check_grad ()
{
    int i;
    for (i=1; i<=n; i++)
        if (v[i].size()%2)
            return 0;
    return 1;
}

void sterge (int x, int y)
{
    v[x].pop_front();
    for (it=v[y].begin(); it!=v[y].end(); ++it)
        if (*it==x)
        {
            v[y].erase(it);
            break;
        }
}

void euler (int nod)
{
    int aux;
    while (true)
    {
        if (v[nod].empty())
            break;
        aux=v[nod].front();
        s.push(nod);
        sterge(nod,aux);
        nod=aux;
    }
}

void solve ()
{
    int crt=1;
    do
    {
        euler(crt);
        crt=s.top();
        s.pop();
        sol[++k]=crt;
    } while (!s.empty());
}

int main ()
{
    int crt,m,i,x,y;
    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);
        v[x].push_back(y);
        v[y].push_back(x);
    }
    if (check_grad()==0)
        printf("-1\n");
    else
    {
        solve();
        for (i=k; i>=1; i--)
            printf("%d ",sol[i]);
        printf("\n");
    }
    return 0;
}