Cod sursa(job #3334522)

Utilizator alinavoroalina voro alinavoro Data 18 ianuarie 2026 12:02:33
Problema Ciclu Eulerian Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.66 kb
#include <algorithm>
#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

const int NMAX= 100'000;
const int MMAX = 500'000;

int N,M;

vector<pair<int,int>> G[NMAX +1];
//in graf avem lista de adiacenta + muchia asociata

ofstream fout("ciclueuler.out");

void ReadInput() {
    ifstream fin("ciclueuler.in");
    fin>>N>>M;
    for(int i=1;i<=M;i++) {
        int u,v;
        fin>>u>>v;
        G[u].push_back(make_pair(v,i));
        G[v].push_back(make_pair(u,i));
    }
    fin.close();
}

bool visited[MMAX+1];
vector<int> ciclu_eulerian;

void FleuryAlgorithm(int nod) {
    while (G[nod].size() > 0) {
        auto [vecin, ind_muchie] = G[nod].back();
        G[nod].pop_back();
        if (visited[ind_muchie] == 1) continue;
        visited[ind_muchie] = 1;
        FleuryAlgorithm(vecin);
        ciclu_eulerian.push_back(vecin);
    }
}

void solveCicluEulerian() {
    for (int i = 1; i <= M ;i++) {
        visited[i] = 0;
    }
    ciclu_eulerian.clear();
    FleuryAlgorithm(1);

    bool single_connected_component = true;
    for (int i = 1; i <= M; i++) {
        if (visited[i] == 0) {
            single_connected_component = false;
        }
    }
    if (single_connected_component == false)
        fout<<-1;
    else {
        for (int nod: ciclu_eulerian) {
            fout<<nod<<" ";
        }
    }
}

int main() {
    ReadInput();

    bool grade_pare = true;
    for (int i = 1; i <= N; i++) {
        if (G[i].size() %2 != 0) {
            grade_pare = false;
        }
    }
    if (grade_pare == false) fout<<-1;
    else solveCicluEulerian();
    return 0;
}