Cod sursa(job #870634)

Utilizator CosminnnChirica Cosmin Cosminnn Data 3 februarie 2013 19:11:22
Problema Ciclu Eulerian Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.31 kb
#include <fstream>
#include <algorithm>
#include <vector>
#include <iostream>

using namespace std;

bool viz[500100];
int n, m, X[500100], Y[500100], sol[500100], nsol;
vector <int> G[100010];

inline void Read()
{
    ifstream f("ciclueuler.in");
    f>>n>>m;
    int i;
    for (i=1; i<=m; i++)
    {
        f>>X[i]>>Y[i];
        G[X[i]].push_back(i);
        G[Y[i]].push_back(i);
    }
    f.close();
}

inline bool Verificare()
{
    for (int i=1; i<=n; i++)
        if (G[i].size() & 1)//daca este impar
            return true;
    return false;
}

inline void DFS(int nod)
{
    vector <int>::iterator it;

    for (it = G[nod].begin(); it!=G[nod].end(); it++)
    {
        if (!viz[*it])
        {
            viz[*it] = true;
            DFS(X[*it] + Y[*it] - nod);
            // daca nod = x -> trebuie sa te duci in y
            // => x+y-x = y rezulta dfs(y);

        }
    }
    sol[++nsol] = nod;
}

inline void Write()
{
    ofstream g("ciclueuler.out");
    int i;
    for (i=1; i<=nsol; i++)
        g<<sol[i]<<" ";
    g<<"\n";
    g.close();
}
int main()
{
    Read();
    if (Verificare())
    {
        ofstream g("ciclueuler.out");
        g<<"-1\n";
        g.close();
        return 0;
    }
    DFS(1);
    Write();
    return 0;
}