Cod sursa(job #2696729)

Utilizator Andrei012Trache Andrei Andrei012 Data 16 ianuarie 2021 13:58:42
Problema Ciclu Eulerian Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.86 kb
#include <bits/stdc++.h>

using namespace std;

int a[500001], b[500001], sol[500001], nr;
bool viz[500001];
vector <int> v[100001];

void euler(int x) {
  int current, urm;
  while(v[x].size()!=0) {
    current=v[x].back();
    v[x].pop_back();
    if(viz[current]==0) {
      viz[current]=1;
      if(a[current]==x)
        urm=b[current];
      else
        urm=a[current];
      euler(urm);
    }
  }
  sol[++nr]=x;
}

int main() {
  int st, i, n, m;
  ifstream cin("ciclueuler.in");
  ofstream cout("ciclueuler.out");

  cin>>n>>m;
  for(i=1;i<=m;i++) {
    cin>>a[i]>>b[i];
    v[a[i]].push_back(i);
    v[b[i]].push_back(i);
  }
  st=0;
  for(i=1;i<=n;i++)
    if((v[i].size()%2)==1)
      st=1;
  if(st==1)
    cout<<-1;
  else {
    euler(1);
    int r;
    for(r=1;r<nr;r++)
        cout<<sol[r]<<" ";
  }
  return 0;
}