Cod sursa(job #3336333)

Utilizator Robi27Baciu Roberto Robi27 Data 24 ianuarie 2026 16:20:20
Problema Ciclu Eulerian Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.51 kb
#include <iostream>
#include <fstream>

using namespace std;
ifstream fin("ciclueuler.in");
ofstream fout("ciclueuler.out");
const int NMAX = 100000;
const int MMAX = 500000;
int N,M;
vector<pair<int, int> > adj[NMAX+1];
bool visited[MMAX+1];
vector<int> ciclu_eulerian;
void fleury(int nod) {
    while (adj[nod].size() > 0) {
        auto [vecin, ind_muchie] = adj[nod].back();
        adj[nod].pop_back();
        if (visited[ind_muchie]) continue;
        visited[ind_muchie] = true;
        fleury(vecin);
        ciclu_eulerian.push_back(vecin);
    }
}
void solve_ciclu_eulerian() {
    for (int i = 1; i<=M; i++) {
        visited[i] = false;
    }
    ciclu_eulerian.clear();
    fleury(1);
    bool single_component = true;
    for (int i = 1; i <= M; i++) {
        if (visited[i] == false) {
            single_component = false;
        }
    }
    if (single_component == false) {
        fout << -1 << '\n';
    }
    else {
        // reverse(ciclu_eulerian.begin(), ciclu_eulerian.end());
        for (int nod : ciclu_eulerian) {
            fout << nod << ' ';
        }
    }

}
int main() {
    fin >> N >> M;
    for (int i = 0; i < M; i++) {
        int x,y;
        fin >> x>> y;
        adj[x].push_back(make_pair(y,i+1));
        adj[y].push_back(make_pair(x,i+1));
    }
    bool grade_pare = true;
    for (int nod = 1; nod <= N; nod++) {
        if (adj[nod].size() % 2 == 1) {
            grade_pare = false;
        }
    }
    if (!grade_pare) fout<< -1 << '\n';
    else solve_ciclu_eulerian();
    return 0;
}