Cod sursa(job #2151358)

Utilizator BaldurCronos Baldur Data 4 martie 2018 13:27:41
Problema Ciclu Eulerian Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 1.27 kb
#include <iostream>
#include <fstream>
#include <vector>
#define N 100005
#define M 500005
using namespace std;
ifstream in("ciclueuler.in");
ofstream out("ciclueuler.out");
vector<pair<int,int> > v[N];
int n, m, g[N], sol[N], szSol, vz[M];

void dfs(int node) {
        while (v[node].size() > 0) {
                int nextNode = v[node].back().first, edge = v[node].back().second;
                v[node].pop_back();

                if (!vz[edge]) {
                        vz[edge] = 1;
                        dfs(nextNode);
                }
        }

        szSol++;
        sol[szSol] = node;
}

int main() {
        int x, y;
        in >> n >> m;

        for (int i = 1; i <= m; i++) {
                in >> x >> y;
                v[x].push_back(make_pair(y, i));
                v[y].push_back(make_pair(x, i));
                if (x != y) {
                        g[x]++;
                        g[y]++;
                }
        }

        for (int i = 1; i <= n; i++) {
                if (g[i] % 2 == 1) {
                        out << -1;
                        return 0;
                }
        }

        dfs(1);
        for (int i = 1; i < szSol; i++) {
                out << sol[i] << " ";
        }
        return 0;
}