Cod sursa(job #2815195)

Utilizator As932Stanciu Andreea As932 Data 9 decembrie 2021 11:44:52
Problema Ciclu Eulerian Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.08 kb
#include <bits/stdc++.h>

using namespace std;

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

const int nmax = 1e5 + 5;
const int mmax = 5e5 + 5;
int n, m, k;
int ans[mmax];
bool vis[mmax];
vector < pair<int,int> > v[nmax];

void read(){
    fin >> n >> m;

    for(int i = 1; i <= m; i++){
        int x, y;
        fin >> x >> y;
        v[x].push_back(make_pair(y, i));
        v[y].push_back(make_pair(x, i));
    }
}

bool not_ok(){
    for(int i = 1; i <= n; i++)
        if(v[i].size() % 2 != 0)
            return true;

    return false;
}

void solve(int x){
    while(!v[x].empty()){
        int y = v[x].back().first;
        int nr = v[x].back().second;

        v[x].pop_back();

        if(!vis[nr]){
            vis[nr] = true;
            solve(y);
        }
    }

    ans[++k] = x;
}

void print_sol(){
    for(int i = 1; i < k; i++)
        fout << ans[i] << " ";
}

int main()
{
    read();
    if(not_ok())
        fout << "-1";
    else{
        solve(1);
        print_sol();
    }

    return 0;
}