Cod sursa(job #2152171)

Utilizator osiaccrCristian Osiac osiaccr Data 5 martie 2018 12:13:48
Problema Ciclu Eulerian Scor 80
Compilator cpp Status done
Runda Arhiva educationala Marime 1.04 kb
#include <fstream>
#include <vector>
#define DEFN 100010
#define DEFM 500010

using namespace std;

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

vector < pair < int, int > > L[DEFN];

int n, m;

bool M[DEFM];

vector < int > Sol;

bool dfs (int v) {
    if (L[v].size () % 2 == 1)
        return false;

    bool is_euler = true;

    for (int i = 0; i < L[v].size (); ++ i) {
        pair < int, int > u = L[v][i];
        if (M[u.second] == 0) {
            M[u.second] = 1;
            if (dfs (u.first) == false)
                is_euler = false;
        }
    }
    Sol.push_back (v);
    return is_euler;
}

int main () {
    fin >> n >> m;
    for (int i = 1; i <= m; ++ i) {
        int x, y;
        fin >> x >> y;
        L[x].push_back (make_pair (y, i));
        L[y].push_back (make_pair (x, i));
    }

    if (dfs (1) == false) {
        fout << -1;
        return 0;
    }

    for (int i = 0; i < Sol.size (); ++ i) {
        fout << Sol[i] << " ";
    }

    return 0;
}