Cod sursa(job #2374763)

Utilizator herbertoHerbert Mohanu herberto Data 7 martie 2019 20:21:48
Problema Ciclu Eulerian Scor 80
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.96 kb
#include<bits/stdc++.h>
using namespace std;
#define MAXN 100001
#define MAXM 500001

struct edge {
  int dest;
  int ord;
};

bool f[MAXM];
vector<edge>g[MAXN];
vector<int>stiv;
int grad[MAXN];

FILE*fout;
void euler(int nod){
  int i;
  for(i=0; i<g[nod].size(); i++)
    if(f[g[nod][i].ord]==0){
      f[g[nod][i].ord]=1;
      euler(g[nod][i].dest);
      }

  stiv.push_back(nod);
}

int main(){
  FILE*fin=fopen("ciclueuler.in", "r");
  fout=fopen("ciclueuler.out", "w");
  int n, m, i, a, b;
  fscanf(fin, "%d%d", &n, &m);
  for(i=1; i<=m; i++){
    f[i]=0;
    fscanf(fin, "%d%d", &a, &b);
    g[a].push_back({b, i});
    g[b].push_back({a, i});
  }
  int ok=1;
  for(i=1; i<=n; i++){
    grad[i]=g[i].size();
    if(g[i].size()%2==1)
      ok=0;
  }
  if(ok==0)
    fprintf(fout, "-1");
  else{
    euler(1);
    while(stiv.size()>1){
      fprintf(fout, "%d ", stiv.back());
      stiv.pop_back();
    }
  }
  return 0;
}