Cod sursa(job #1131756)

Utilizator darrenRares Buhai darren Data 1 martie 2014 13:43:25
Problema Ciclu Eulerian Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 1.2 kb
#include <fstream>
#include <algorithm>
#include <vector>

using namespace std;

int N, M;
int E1[500002], E2[500002];
bool nok[500002];
vector<int> V[100002], result;

void Dfs(int x)
{
    for (vector<int>::iterator it = V[x].begin(); it != V[x].end(); ++it)
        if (!nok[*it])
        {
            int nod;
            if (E1[*it] == x) nod = E2[*it];
            else              nod = E1[*it];

            nok[*it] = true;

            Dfs(nod);
        }

    result.push_back(x);
}

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

    fin >> N >> M;
    for (int i = 1; i <= M; ++i)
    {
        fin >> E1[i] >> E2[i];
        V[E1[i]].push_back(i);
        V[E2[i]].push_back(i);
    }

    bool ok = true;
    for (int i = 1; i <= N; ++i)
        if (V[i].size() % 2 == 1)
        {
            ok = false;
            break;
        }

    if (!ok)
    {
        fout << -1 << '\n';
        fin.close();
        fout.close();
        return 0;
    }

    Dfs(1);

    for (int i = 0; i < int(result.size()); ++i)
        fout << result[i] << ' ';
    fout << '\n';

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