Cod sursa(job #3268300)

Utilizator divadddDavid Curca divaddd Data 14 ianuarie 2025 13:47:33
Problema Ciclu Eulerian Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.26 kb
#include <bits/stdc++.h>
using namespace std;
const int NMAX = 1e5+2;
const int MMAX = 5e5+2;
using pii = pair<int, int>;
int n,m;
bool used[MMAX],vis[NMAX];
vector<pii> v[NMAX];

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

vector<int> findEulerCycle(){
  stack<int> st;
  vector<int> g(n+1);
  for(int i = 1; i <= n; i++){
    g[i] = v[i].size();
  }
  st.push(1);
  vector<int> ans;
  while(!st.empty()){
    int nod = st.top();
    vis[nod] = true;
    if(g[nod] == 0){
      ans.push_back(nod);
      st.pop();
    }else{
      int len = v[nod].size();
      auto [vecin, idx] = v[nod][len-g[nod]];
      if(used[idx] == false){
        st.push(vecin);
        used[idx] = true;
      }
      g[nod]--;
    }
  }
  return ans;
}

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