Cod sursa(job #902209)

Utilizator lianaliana tucar liana Data 1 martie 2013 13:16:28
Problema Ciclu Eulerian Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 1.65 kb
#include<stdio.h>
#include<list>
using namespace std;
#define nmax 100005
long n, m, i, a, b, gr[nmax], ac, urm, el;
list <long> ma[nmax], li;
list <long> ::iterator it, poz, inc;
bool viz[nmax], ok;

void citire()
{
    scanf("%ld %ld",&n,&m);
    for (i=1;i<=m;i++)
    {
        scanf("%ld %ld",&a,&b);
        ma[a].push_back(b); gr[a]++;
        ma[b].push_back(a); gr[b]++;
    }
}

void dfs(long nod)
{
    list <long> ::iterator it;
    viz[nod]=1;
    for (it=ma[nod].begin();it!=ma[nod].end();it++)
        if (viz[*it]==0)
            dfs(*it);
}

void verificare()
{
    ok=1;
    for (i=1;i<=n;i++)
        ok=(ok&&viz[i]&&(gr[i]%2==0));
}

void extindere(long nod)
{
    ac=nod;  poz=inc;   poz++;
    while (1)
    {
        urm=*ma[ac].begin();
        li.insert(poz,urm);
        //sterge muchie
        ma[ac].erase(ma[ac].begin());
        for (it=ma[urm].begin();it!=ma[urm].end();it++)
            if(*it==ac)
            {   ma[urm].erase(it);  break;  }
        ac=urm;
        if (ac==nod)
            break;
    }
}

void rezolvare()
{
    li.push_back(1);   li.push_back(0);
    inc=li.begin();
    while (li.size()<m+1)
    {
        el=*inc;
        if (ma[el].size())
            extindere(el);
        inc++;
    }
}

int main()
{
    freopen("ciclueuler.in","r",stdin);
    freopen("ciclueuler.out","w",stdout);
    citire();
    dfs(1);
    verificare();
    if (!ok)
        printf("-1\n");
    else
    {
        rezolvare();
        li.pop_back();    li.pop_back();
        for (it=li.begin();it!=li.end();it++)
                printf("%ld ",*it);
    }
    return 0;
}