Cod sursa(job #2549614)

Utilizator andra1782Andra Alazaroaie andra1782 Data 17 februarie 2020 20:49:17
Problema Ciclu Eulerian Scor 50
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.95 kb
#include <stdio.h>
#include <vector>
#include <stack>
#define MAXN 100000
char viz[MAXN+1];
struct edge{
  int y,poz;
};
std::vector<edge>v[MAXN+1];
std::stack<int>s,r;
int main(){
  FILE *fin=fopen("ciclueuler.in","r");
  FILE *fout=fopen("ciclueuler.out","w");
  int n,m,i,x,y;

  fscanf(fin,"%d%d",&n,&m);
  for(i=0; i<m; i++){
    fscanf(fin,"%d%d",&x,&y);
    v[x].push_back({y,i});
    v[y].push_back({x,i});
  }
  i=1;
  while(i<=n && !(v[i].size()%2))
      i++;
  if(i>n){
    s.push(1);
    while(!s.empty()){
      int f=s.top();
      if(!v[f].empty()){
        edge x=v[f].back();
        v[f].pop_back();
        if(!viz[x.poz]){
          viz[x.poz]=1;
          s.push(x.y);
        }
      }else{
        r.push(f);
        s.pop();
      }
    }
    while(!r.empty()){
      fprintf(fout,"%d ",r.top());
      r.pop();
    }
  }else
    fprintf(fout,"-1\n");
  fclose(fin);
  fclose(fout);
  return 0;
}