Cod sursa(job #3208202)

Utilizator AdrianRosuRosu Adrian Andrei AdrianRosu Data 27 februarie 2024 22:52:00
Problema Ciclu Eulerian Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.02 kb
#include <bits/stdc++.h>
#define DIM 200001

using namespace std;

ifstream fin("ciclueuler.in");

ofstream fout("ciclueuler.out");

struct elem{

    int x, ok;

};

stack <int> stk;

vector < elem > G[DIM];

int used[3 * DIM];

int n, m, x, y, idx;

void Euler(int node){

    while(G[node].size()){

        int pos = G[node].size() - 1;

        int next = G[node][pos].x;

        int ok = G[node][pos].ok;

        G[node].pop_back();

        if(used[ok])

            continue;

        used[ok] = 1;

        Euler(next);

    }

    stk.push(node);

}

int main(){

    fin >> n >> m;

    while(m--){

        fin >> x >> y;

        ++idx;

        G[x].push_back({y, idx});

        G[y].push_back({x, idx});

    }

    for(int i=1;i<=n;i++)

        if(G[i].size() % 2 == 1){

            fout << -1;

            return 0;

        }

    Euler(1);

    while(stk.size() > 1){

        fout << stk.top() << " ";

        stk.pop();

    }

}