Cod sursa(job #2924690)

Utilizator apocal1ps13Stefan Oprea Antoniu apocal1ps13 Data 8 octombrie 2022 15:44:39
Problema Ciclu Eulerian Scor 10
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.04 kb
#include<algorithm>
#include<iostream>
#include<fstream>
#include<stack>
#include<vector>
#define NMAX 100001
using namespace std;
ifstream in("ciclueuler.in");
ofstream out("ciclueuler.out");
vector<int>g[NMAX], sol, deg(NMAX);
stack<int>st;
int n, x, y, m;
void euler(int& node) {
    int oth = 0;
    while (!g[node].empty()) {
        st.push(node);
        oth = g[node].back();
        g[node].pop_back();
        g[oth].erase(find(g[oth].begin(), g[oth].end(), node));
        node = oth;
    }
}
int main() {
    in >> n >> m;
    while (m--) {
        in >> x >> y;
        g[x].push_back(y);
        g[y].push_back(x);
        deg[x]++;
        deg[y]++;
    }
    for (int i = 1; i <= n; i++)
        if (deg[i] % 2) {
            out << -1;
            return 0;
        }
    sol.push_back(1);
    int node = 1, nr = 0;
    do {
        euler(node);
        sol.push_back(st.top());
        st.pop();
    } while (!st.empty());
    sol.pop_back();
    for (auto i : sol) out << i << " ";
    return 0;
}