Cod sursa(job #3330143)

Utilizator Andrei-Dani-10Pisla Andrei Daniel Andrei-Dani-10 Data 17 decembrie 2025 20:27:40
Problema Ciclu Eulerian Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.17 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){

    for(; !muchii[node].empty(); ){

        pii edge = muchii[node].back();
        muchii[node].pop_back();

        if(usededges[edge.y]){ continue; }

        usededges[edge.y] = 1;
        dfscheckeuler(edge.x);
    }

    euleredges.push_back(node);

    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;
}