Cod sursa(job #774637)

Utilizator SteveStefan Eniceicu Steve Data 6 august 2012 10:55:03
Problema Ciclu Eulerian Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.48 kb
#include <fstream>
#include <queue>
#include <iostream>

using namespace std;

int N, M;
int x[100005], j = -1;
deque <pair <int, int> > v[100005];
int muchii[100005];

void Citire () {
    ifstream fin ("ciclueuler.in");
    fin >> N >> M;
    int a, b;
    for (int i = 0; i < M; i++)
    {
        fin >> a >> b;
        v[a].push_back (make_pair (b, v[b].size ()));
        v[b].push_back (make_pair (a, v[a].size () - 1));
        muchii[a]++;
        muchii[b]++;
    }
    fin.close ();
}

void Business () {
    int nod = 1, a, b;
    while (M) {
        x[++j] = nod;
        if (muchii[v[nod].back ().first] >= 2)
        {
            a = v[nod].back ().first;
            b = v[nod].back ().second;
            v[nod].pop_back ();
        }
        else
        {
            a = v[nod].front ().first;
            b = v[nod].front ().second;
            v[nod].pop_front ();
        }
        v[a].erase (v[a].begin () + b);
        muchii[a]--;
        muchii[nod]--;
        M--;
        nod = a;
    }
    /*for (int i = 1; i <= N; i++)
        cout << v[i].size () << " ";
    cout << "\n";*/
    for (int i = 0; i <= j; i++)
        cout << x[i] << " ";
}

int main () {
    Citire ();
    ofstream fout ("ciclueuler.out");
    for (int i = 1; i <= N; i++)
    {
        if (muchii[i] & 1)
        {
            cout << "-1";
            fout.close ();
            return 0;
        }
    }
    Business ();
    return 0;
}