Cod sursa(job #447708)

Utilizator yrarBogdan Ionut yrar Data 30 aprilie 2010 17:56:30
Problema Ciclu Eulerian Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.26 kb
#include <fstream>
#define nmax 1000

using namespace std;

ifstream f("ciclueuler.in");
ofstream g("ciclueuler.out");

struct lista
{
    int nod;
    lista *urm;
} *G[nmax];

int N, M, A[nmax][nmax], C[nmax], S, ok=1;

/*
void add(int i, int j)
{
    lista *p;
    p = new lista;
    p -> nod = j;
    p -> urm = G[i];
    G[i] = p;
}
*/
void euler(int nod)
{
    /* lista *p; */
    /*
    for(p = G[nod]; p; p -> urm)
    {
        if(!U[nod][p->nod])
        {
            U[nod][p->nod] = 1;
            U[p->nod][nod] = 1;
            euler(p->nod);
        }
    }
    */
    for(int i=1; i<=N; ++i)
    {
        if(A[nod][i])
        {
            A[nod][i] = 0;
            A[i][nod] = 0;
            euler(i);
        }
    }
    C[++S] = nod;
}

void verif()
{
    for(int i=1; i<=N; ++i)
        if(A[i][0]%2==1)
        {
            ok=0;
            return;
        }
}

int main()
{
    int i, x, y;
    f >> N >> M;
    for(; M>0; --M)
    {
        f >> x >> y;
        A[x][0]++;
        A[y][0]++;
        A[x][y] = 1;
        A[y][x] = 1;
    }
    verif();
    if(ok)
    {
        euler(1);
        for(i=1; i<=S; ++i) g << C[i] << " ";
    }
    else g << "-1";
    return 0;
}