Cod sursa(job #1343346)

Utilizator rogoz.bogdanRogoz Bogdan rogoz.bogdan Data 15 februarie 2015 12:50:46
Problema Ciclu Eulerian Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 1.27 kb
#include <fstream>
#include <vector>
#include <utility>
#define NX 100001
#define MX 500001
using namespace std;

int n,m;
vector< pair<int, int> > v[NX];
bool viz[MX];

ifstream fin("ciclueuler.in");
ofstream fout("ciclueuler.out");

void citire()
{
    int i,x,y;
    pair<int, int> muchie;
    fin>>n>>m;
    for(i=1; i<=m; i++)
    {
        fin>>x>>y;
        muchie.first = y;
        muchie.second = i;
        v[x].push_back(muchie);

        muchie.first = x;
        v[y].push_back(muchie);
    }
}

int grad_par()
{
    int i;
    for(i=1; i<=n; i++)
    {
        if(v[i].size() % 2 == 1) return 0;
    }

    return 1;
}

void hierholzer()
{
    pair<int, int> e;
    int i=1;

    fout<<1<<' ';
    while(!v[i].empty())
    {
        e = v[i].back();
        v[i].pop_back();
        if(!viz[e.second])
        {
            viz[e.second] = 1;
            if(e.first == 1) break;
            else
            {
                fout<<e.first<<' ';
                i = e.first;
            }
        }
    }
    fout<<'\n';
}

int main()
{
    citire();
    if(grad_par() == 0)
    {
        fout<<-1<<'\n';
    }
    else
    {
        hierholzer();
    }

    fin.close(); fout.close();
    return 0;
}