Cod sursa(job #2696730)

Utilizator stef2003Bud Stefan stef2003 Data 16 ianuarie 2021 14:01:56
Problema Ciclu Eulerian Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.9 kb
#include <iostream>
#include <cstdio>
#include <vector>
#include <fstream>

using namespace std;

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

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;
  fin>>n>>m;
  for(i=1;i<=m;i++) {
    fin>>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)
    fout<<"-1";
  else {
    euler(1);
    for(;nr>1;nr--)
      fout<<sol[nr]<<" ";
  }
  return 0;
}