Cod sursa(job #3330719)

Utilizator DragosC1Dragos DragosC1 Data 21 decembrie 2025 15:32:00
Problema Ciclu Eulerian Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.22 kb
#include <bits/stdc++.h>
#include <fstream>
using namespace std;

int n, m;
vector<pair<int, int>> G[100001];
bool viz[500001];

ifstream f("ciclueuler.in");
ofstream g("ciclueuler.out");

void ReadInput() {
    f >> n >> m;
    for (int i = 1; i <= m; i++) {
        int x, y;
        f >> x >> y;
        G[x].push_back({y, i});
        G[y].push_back({x, i});
    }
}

vector<int> ciclu;

void dfs(int nod) {
    while (G[nod].size() > 0) {
        auto it = G[nod].back();
        G[nod].pop_back();
        int vecin = it.first;
        int id_muchie = it.second;
        if (viz[id_muchie])
            continue;
        viz[id_muchie] = 1;
        dfs(vecin);
        ciclu.push_back(vecin);
    }
}

void FindEulerianCycle() {
    for (int i = 1; i <= m; i++)
        viz[i] = 0;
    dfs(1);
    for (int i = 1; i <= m; i++)
        if (!viz[i]) {
            g << "-1\n";
            return;
        }
    reverse(ciclu.begin(), ciclu.end());
    for (auto x : ciclu)
        g << x << " ";
}

int main() {
    ReadInput();
    bool ok = 1;
    for (int i = 1; i <= n; i++)
        if (G[i].size() % 2 != 0) {
            ok = 0;
            break;
        }
    if (ok)
        FindEulerianCycle();
    else
        g << "-1\n";
    return 0;
}