Cod sursa(job #3002209)

Utilizator SerbanCaroleSerban Carole SerbanCarole Data 14 martie 2023 15:23:59
Problema Ciclu Eulerian Scor 80
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.35 kb
#include <fstream>
#include <bitset>
#include <vector>
using namespace std;

ifstream cin("ciclueuler.in");
ofstream cout("ciclueuler.out");

const int MAX = 1e5;

struct muchie{

    int y , i;

};

int n , m , gr[MAX] , s[MAX] , x , y;

vector <int> e;
vector <muchie> g[MAX+1];
bitset <MAX*5+1> b;
bitset <MAX+1> marcat;

void dfs( int x ){

    marcat[x] = 1;

    for(auto it:g[x]){

        if(!marcat[it.y]){

            dfs(it.y);
        }
    }
}

void euler( int x ){

    for(int i = s[x] ; i < gr[x] ; i++){

        s[x]++;

        if(!b[g[x][i].i]){

            b[g[x][i].i] = 1;

            euler(g[x][i].y);

        }
    }

    e.push_back(x);
}

int main(){

    cin >> n >> m;

    for(int i = 1 ; i <= m ; i++){

        cin >> x >> y;

        g[x].push_back({y,i});
        g[y].push_back({x,i});
        gr[x]++;
        gr[y]++;
    }

    dfs(1);

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

        if(gr[i]%2){

            cout << -1;

            exit(0);

        }else{

            if(!marcat[i])

                if(gr[i]){

                    cout << -1;

                    exit(0);
                }
        }
    }

    euler(1);

    int h = e.size();

    for(int i = 1 ; i < h ; i++){

        cout << e[i] << ' ';
    }

    return 0;
}