Cod sursa(job #3208193)

Utilizator AdrianRosuRosu Adrian Andrei AdrianRosu Data 27 februarie 2024 22:32:47
Problema Ciclu Eulerian Scor 80
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.09 kb
#include <bits/stdc++.h>
#define DIM 100001

using namespace std;

ifstream fin("ciclueuler.in");

ofstream fout("ciclueuler.out");

struct elem{

    int x, ok;

};

stack <int> stk;

vector < elem > G[DIM];

int n, m, x, y, idx;

void Euler(int node){

    for(int i=0;i<G[node].size();i++){

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

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

        if(!ok)

            continue;

        G[node][i].ok = 0;

        for(int j=0;j<G[next].size();j++)

            if(G[next][j].x == node && G[next][j].ok){

                G[next][j].ok = 0;

                break;

            }

        Euler(next);

    }

    stk.push(node);

}

int main(){

    fin >> n >> m;

    while(m--){

        fin >> x >> y;

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

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

    }

    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();

    }

}