Cod sursa(job #3268180)

Utilizator divadddDavid Curca divaddd Data 13 ianuarie 2025 20:37:05
Problema Ciclu Eulerian Scor 50
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.98 kb
#include <bits/stdc++.h>
using namespace std;
const int NMAX = 1e5+2;
using pii = pair<int, int>;
int n,m,g[NMAX],num[NMAX];
bool used[NMAX],vis[NMAX];
vector<pii> v[NMAX];
vector<int> cycle;

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

void dfs(int nod){
  vis[nod] = true;
  for(int i = num[nod]; i < v[nod].size(); i++){
    num[nod]++;
    auto [vecin, idx] = v[nod][i];
    if(used[idx] == false){
      used[idx] = true;
      dfs(vecin);
    }
  }
  cycle.push_back(nod);
}

int main() {
  fin >> n >> m;
  for(int i = 1; i <= m; i++){
    int x, y;
    fin >> x >> y;
    g[x]++;
    g[y]++;
    v[x].push_back({y, i});
    v[y].push_back({x, i});
  }
  bool ok = true;
  for(int i = 1; i <= n; i++){
    ok &= (g[i]%2 == 0);
  }
  dfs(1);
  for(int i = 1; i <= n; i++){
    ok &= vis[i];
  }
  if(ok){
    cycle.pop_back();
    for(int it: cycle){
      fout << it << " ";
    }
  }else{
    fout << "-1";
  }
  return 0;
}