Cod sursa(job #3298213)

Utilizator paulihno15Ciumandru Paul paulihno15 Data 28 mai 2025 08:56:57
Problema Ciclu Eulerian Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.2 kb
#include <bits/stdc++.h>
#define NMAX 100000
#define MMAX 500000

using namespace std;

ifstream fin("ciclueuler.in");
ofstream fout("ciclueuler.out");

int n, m, a, b;
vector<vector<pair<int, int>>> graf(NMAX + 2);
vector<bool> viz_nod(NMAX + 2), viz_mch(MMAX + 2);
vector<int> grad(NMAX + 2), sol;

void DFS(int nod) {
    viz_nod[nod] = 1;
    for (auto it : graf[nod]) {
        if (!viz_nod[it.first]) {
            DFS(it.first);
        }
    }
}

void Euler(int nod) {
    while (graf[nod].size()) {
        int vec = graf[nod].back().first;
        int urm_mch = graf[nod].back().second;
        graf[nod].pop_back();
        if (!viz_mch[urm_mch]) {
            viz_mch[urm_mch] = 1;
            Euler(vec);
        }
    }
    sol.emplace_back(nod);
}

int main() {
    fin >> n >> m;
    for (int i = 1; i <= m; i++) {
        fin >> a >> b;
        grad[a]++;
        grad[b]++;
        graf[a].push_back({b, i});
        graf[b].push_back({a, i});
    }

    DFS(1);

    for (int i = 1; i <= n; i++) {
        if (!viz_nod[i] || grad[i] & 1) {
            fout << -1;
            return 0;
        }
    }

    Euler(1);
    sol.pop_back();
    for (auto &nod : sol) {
        fout << nod << ' ';
    }
    return 0;
}