Cod sursa(job #3283294)

Utilizator Mateixx1Trandafir matei Mateixx1 Data 8 martie 2025 22:10:44
Problema Ciclu Eulerian Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.16 kb
#include <iostream>
#include <vector>
#include <fstream>
#include <stack>
#include <bitset>
using namespace std;
ifstream f("ciclueuler.in");
ofstream g("ciclueuler.out");
const int NMAX=100010,MMAX=500100;
int n,x,y,m;
struct muchie {
    int nod,nrm;/// nrm = numarul muchiei
};
vector<muchie>G[NMAX];
vector<int>L;
stack<int>S;
bitset<MMAX>elim;

void euler() {
    muchie mm;
    S.push(1);
    while(!S.empty()) {
        int k=S.top();
        if(G[k].size()>0) {
            mm=G[k].back();
            G[k].pop_back();
            if(elim[mm.nrm]==0) {
                elim[mm.nrm]=1;
                S.push(mm.nod);
            }
        } else {
            L.push_back(k);
            S.pop();
        }
    }
}

int main() {
    f>>n>>m;
    for(int i=1; i<=m; i++) {
        f>>x>>y;
        G[x].push_back({y,i});
        G[y].push_back({x,i});
    }
    for(int i=1; i<=n; i++) {
        if(G[i].size()&1) {
            g<<"-1";
            return 0;
        }
    }
    euler();
    L.pop_back();
    for(int i=L.size()-1; i>=0; i--) {
        g<<L[i]<<' ';
    }
    f.close();
    g.close();
    return 0;
}