Cod sursa(job #2705812)

Utilizator FunnyStockyMihnea Andreescu FunnyStocky Data 13 februarie 2021 12:50:49
Problema Ciclu Eulerian Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.14 kb
#include <cstdio>
#include <vector>

using namespace std;

const int N = 100000 + 7;
const int M = 500000 + 7;
int n, m, x[M];
vector<int> g[N], ret;

void dfs(int a) {
        while (!g[a].empty()) {
                int i = g[a].back(), b;
                g[a].pop_back();
                if (x[i] == -1)
                        continue;
                b = x[i] ^ a;
                x[i] = -1;
                dfs(b);
        }
        ret.push_back(a);
}

int main() {
        freopen ("ciclueuler.in", "r", stdin);
        freopen ("ciclueuler.out", "w", stdout);

        scanf("%d %d", &n, &m);
        for (int i = 1; i <= m; i++) {
                int a, b;
                scanf("%d %d", &a, &b);
                x[i] = (a ^ b);
                g[a].push_back(i);
                g[b].push_back(i);
        }
        for (int i = 1; i <= n; i++)
                if ((int) g[i].size() & 1) {
                        printf("-1\n");
                        return 0;
                }
        dfs(1);
        ret.pop_back();
        for (auto &x : ret)
                printf("%d ", x);
        printf("\n");
}