Cod sursa(job #3330139)

Utilizator Andrei-Dani-10Pisla Andrei Daniel Andrei-Dani-10 Data 17 decembrie 2025 19:47:23
Problema Ciclu Eulerian Scor 50
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.26 kb
#include <fstream>

#include <utility>
#define x first
#define y second

#include <vector>

using namespace std;

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

typedef pair <int, int> pii;
const int nmax = 1e5, kkmax = 5e5;
int n, kk, xx, yy;

vector <pii> muchii[nmax + 2];
int usededges[kkmax + 2];

vector <int> euleredges;

void dfscheckeuler(int node){

    euleredges.push_back(node);

    for(int it = muchii[node].size() - 1; it >= 0; it--){
        it = min(it, int(muchii[node].size()) - 1); if(it < 0){ return; }

        if(usededges[muchii[node][it].y]){ continue; }

        muchii[node].pop_back();

        usededges[muchii[node][it].y] = 1;

        dfscheckeuler(muchii[node][it].x);
    }
    return;
}

int check(){
    int okkk = 0;
    for(int i = 1; i <= n; i++){
        okkk |= (muchii[i].size() & 1);
    }
    return okkk;
}

int main(){

    in>>n>>kk;
    for(int it = 1; it <= kk; it++){
        in>>xx>>yy;
        muchii[xx].push_back(make_pair(yy, it));
        muchii[yy].push_back(make_pair(xx, it));
    }

    if(check()){ out<<"-1\n"; return 0; }

    dfscheckeuler(1);
    euleredges.pop_back();

    for(auto f : euleredges)
        out<<f<<" ";

    return 0;
}