Cod sursa(job #531921)

Utilizator skullLepadat Mihai-Alexandru skull Data 10 februarie 2011 16:52:04
Problema Ciclu Eulerian Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 1.24 kb
#include <stdio.h>
#include <vector>
using namespace std;
#define nmax 100005
#define mx 500005

vector<int> G[nmax];
int sol[nmax];
int N, nr;

void citire ()
{
    int M, i, x, y;
    freopen("ciclueuler.in","r",stdin);
    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);
    }
}

void euler(int nod)
{
    int x;
    vector<int>::iterator it,jt;
    it = G[nod].begin();
    for ( ; it!=G[nod].end() ; )
    {
        x = *it;
        jt = G[x].begin();
        for ( ; jt != G[x].end(); )
        {

            if (*jt == nod)
            {
                G[x].erase(jt);
                break;
            }
            jt++;
        }
        G[nod].erase( G[nod].begin() );
        euler(x);
        it = G[nod].begin();
    }
    sol[++nr] = nod;
}

void solve ()
{
    int i;
    for (i = 1; i <= N; ++i)
        if ( G[i].size()%2) { printf("-1\n"); return; }
    nr = 0;
    euler(1);
}

void afisare ()
{
    int i;
    for (i = nr; i > 1; --i) printf("%d ", sol[i]);
}

int main ()
{
    citire ();
    freopen("ciclueuler.out","w",stdout);
    solve ();
    afisare ();
    return 0;
}