Cod sursa(job #2216288)

Utilizator 24601Dan Ban 24601 Data 26 iunie 2018 11:53:28
Problema Ciclu Eulerian Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.32 kb
#include <cstdio>
#include <set>
#include <utility>
#include <vector>

#define NMAX 100000

static std::vector<std::pair<int, int> > adj[NMAX+1];
static std::set<std::pair<int, int> > deleted[NMAX+1];
static std::vector<int> sol;
static int deg[NMAX+1];

static inline void ciclueuler(int v)
{
    for (std::vector<std::pair<int, int> >::iterator it = adj[v].begin(); it != adj[v].end(); it++) {
        std::set<std::pair<int, int> >::iterator sit = deleted[v].find(*it);
        if (sit == deleted[v].end()) {
            deleted[v].insert(*it);
            deleted[it->first].insert(std::make_pair(v, it->second));
            ciclueuler(it->first);
        }
    }

    sol.push_back(v);
}

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

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

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

    while (m--) {
        scanf("%d %d", &u, &v);
        adj[u].push_back(std::make_pair(v, m));
        deg[u]++;
        deg[v]++;
        if (u != v) {
            adj[v].push_back(std::make_pair(u, m));
            deg[u]++;
            deg[v]++;
        }
    }

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

    ciclueuler(1);

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

    return 0;
}