Cod sursa(job #1914658)

Utilizator AlexNiuclaeNiculae Alexandru Vlad AlexNiuclae Data 8 martie 2017 17:56:07
Problema Ciclu Eulerian Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 1.25 kb
#include <bits/stdc++.h>

using namespace std;

const int nmax = 1e5 + 10;
const int mmax = 5e5 + 10;

int n, m;
int last, st[mmax], used[mmax];
pair < int, int > edge[mmax];
vector < int > g[nmax], ans;

void input() {
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= m; ++i) {
        int x, y;
        scanf("%d %d", &x, &y);

        g[x].push_back(i);
        g[y].push_back(i);

        edge[i] = {x, y};
    }
}

void no_solution() {
    printf("-1\n");
    exit(0);
}

int second_node(int idx, int node) {
    return (edge[idx].first == node) ? edge[idx].second : edge[idx].first;
}

void run_euler() {
    for (int i = 1; i <= n; ++i)
        if ((int)g[i].size()&1)
            no_solution();

    for (int node = 1; ; ) {
        if (g[node].size() == 0)
            break;

        int curr = g[node].back(); g[node].pop_back();
        if (used[curr]) continue;

        used[curr] = 1;
        node = second_node(curr, node);
        ans.push_back(node);
    }
}

void output() {
    for (auto &it: ans)
        printf("%d ", it);
}

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

    input();
    run_euler();
    output();


    return 0;
}