Cod sursa(job #2864491)

Utilizator MocalinnoMoca Andrei Catalin Mocalinno Data 7 martie 2022 22:03:32
Problema Ciclu Eulerian Scor 80
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.13 kb
#include <bits/stdc++.h>
using namespace std;
ifstream fin("ciclueuler.in");
ofstream fout("ciclueuler.out");
using VI  = vector<int>;
using VVI = vector<VI>;
using PII = pair<int, int>;
using VP  = vector<PII>;
using VB  = vector<bool>;
VVI g;
VI ciclu;
VB erased;
VP muchie;
int n, m;
inline void Euler(int const& x) {
    for (int const& ind : g[x])
        if (!erased[ind]) {
            erased[ind] = true;
            int y = muchie[ind].first;
            if (x == y)
                y = muchie[ind].second;
            Euler(y);
        }
    ciclu.emplace_back(x);
}
int main() {
    fin >> n >> m;
    g = VVI(n + 1);
    muchie = VP(m + 1);
    for (int i = 1; i <= m; ++i) {
        int x, y;
        fin >> x >> y;
        muchie[i] = {x, y};
        g[x].emplace_back(i);
        g[y].emplace_back(i);
    }
    for (int i = 1; i <= n; ++i)
        if (g[i].size() % 2) {
            fout << -1;
            return 0;
        }
    erased = VB(m + 1);
    Euler(1);
    ciclu.pop_back();
    for (int const& x : ciclu)
        fout << x << ' ';
    fin.close();
    fout.close();
    return 0;
}