Cod sursa(job #3291332)

Utilizator ciucelizamariaeliza ciuc ciucelizamaria Data 4 aprilie 2025 10:44:42
Problema Ciclu Eulerian Scor 80
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.43 kb
#include <bits/stdc++.h>

using namespace std;

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

///1 2 3 5 4 2 6 3 1

int X[500005], Y[500005];
int indice[100005];
int n, m;
int grd[100005];
stack<int> st;
bitset<500005> viz;
vector<int> L[100005];

void Citire() {
    int x, y;

    fin >> n >> m;
    for(int i = 1; i <= m; i++) {
        fin >> x >> y;
        X[i] = x;
        Y[i] = y;
        L[x].push_back(i);
        L[y].push_back(i);

        grd[x]++;
        grd[y]++;
    }
}

void ToateGradelePare() {
    for(int i = 1; i <= n; i++)
        if(grd[i] % 2 == 1) {
            fout << "IMPOSSIBLE";
            exit(0);
        }
}

void DfsEuler(int nod) {
    int len = L[nod].size();

    while(indice[nod] < len) {
        int muchie = L[nod][indice[nod]];
        indice[nod]++;
        if(!viz[muchie]) {
            viz[muchie] = 1;
            int nod2 = X[muchie] + Y[muchie] - nod;
            DfsEuler(nod2);
        }
    }

    st.push(nod);
}

void Soluion() {
    int len, i;

    DfsEuler(1);
    len = st.size();
    i = 1;
    while(i < len) {
        fout << st.top() << " ";
        st.pop();
        i++;
    }

    fout << "\n";
}

int main() {
    ios_base :: sync_with_stdio(0);
    fin.tie(0);
    fout.tie(0);

    Citire();
    ToateGradelePare();
    Soluion();


    fin.close();
    fout.close();
    return 0;
}