Cod sursa(job #988968)

Utilizator mvcl3Marian Iacob mvcl3 Data 24 august 2013 14:20:46
Problema Ciclu Eulerian Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 1.05 kb
#include <fstream>
#include <vector>
#define IN "ciclueuler.in"
#define OUT "ciclueuler.out"
#define MAX_SIZE 100003

int N, M, K = -1, SOL[MAX_SIZE * 5], X[MAX_SIZE * 5], Y[MAX_SIZE * 5];
bool B[MAX_SIZE];

std :: vector <int> G[MAX_SIZE];
std :: ifstream f(IN);
std :: ofstream g(OUT);

void READ_DATA()
{
    f >> N >> M;
    for(int i = 1; i <= M; ++i)
    {
        f >> X[i] >> Y[i];
        G[ X[i] ].push_back(i);
        G[ Y[i] ].push_back(i);
    }
}

bool ITS_EULERIAN()
{
    for(int i = 1; i <= N; ++i)
        if(G[i].size() % 2) return 0;

    return 1;
}

void EULER(int nod)
{
    std :: vector <int> :: iterator it = G[nod].begin();

    for(; it != G[nod].end(); ++it)
        if(!B[*it])
        {
            B[*it] = 1;
            EULER(X[*it] + Y[*it] - nod);
        }

    SOL[++K] = nod;
}

void WRITE()
{
    if(K == -1) g << "-1\n";
    else        for(int i = 1; i <= K; ++i) g << SOL[i] << ' ';
}

int main()
{
    READ_DATA();
    if( ITS_EULERIAN() )
    {
        K = 0;
        EULER(1);
    }
    WRITE();

    g.close();
    return 0;
}