Cod sursa(job #2216576)

Utilizator 24601Dan Ban 24601 Data 27 iunie 2018 13:19:09
Problema Ciclu Eulerian Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.25 kb
#include <cstdio>
#include <vector>

#define NMAX 100000
#define MMAX 500000

static std::vector<int> adj[NMAX+1], stack;
static int sol[2*MMAX+1], deg[NMAX+1], nsol;

int main()
{
    int n, m, u, v, i;

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

    scanf("%d %d", &n, &m);

    for (i = 1; i <= m; i++) {
        scanf("%d %d", &u, &v);

        adj[u].push_back(v);
        adj[v].push_back(u);

        deg[u]++;
        deg[v]++;
    }

    for (v = 1; v <= n; v++) {
        if (deg[v] & 1) {
            puts("-1");
            return 0;
        }
    }

    stack.push_back(1);
    while (!stack.empty()) {
        v = stack.back();
        stack.pop_back();
        if (!adj[v].empty()) {
            std::vector<int>::iterator it = adj[v].end() - 1;
            adj[v].erase(it);
            for (std::vector<int>::iterator pit = adj[*it].begin();
                    pit != adj[*it].end(); pit++) {
                if (*pit == v) {
                    adj[*it].erase(pit);
                    break;
                }
            }
            stack.push_back(*it);
        } else {
            sol[nsol++] = v;
        }
    }

    for (i = 0; i < nsol - 1; i++) {
        printf("%d ", sol[i]);
    }

    return 0;
}