Cod sursa(job #2910597)

Utilizator mircea_007Mircea Rebengiuc mircea_007 Data 22 iunie 2022 16:58:22
Problema Ciclu Eulerian Scor 80
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.28 kb
// This program was written by Mircea Rebengiuc
// on 22.06.2022
// for problem ciclueuler

#include <stdio.h>
#include <ctype.h>
#include <vector>

#define MAXN 100000
#define MAXM 500000

std::vector<int> adj[MAXN];

int cycle[MAXM + 1];
int sp;

int a[MAXM];
int b[MAXM];
char good[MAXM];

void dfs( int u ){// n-am chef sa fac iterativ
  for( int e : adj[u] )
    if( good[e] ){
      good[e] = 0;
      dfs( a[e] + b[e] - u );
    }

  cycle[sp++] = u;
}

FILE *fin, *fout;

static inline int fgetint(){
  int n = 0, ch;

  while( !isdigit( ch = fgetc( fin ) ) );
  do
    n = n * 10 + ch - '0';
  while( isdigit( ch = fgetc( fin ) ) );

  return n;
}

int main(){
  fin = fopen( "ciclueuler.in", "r" );
  fout = fopen( "ciclueuler.out", "w" );

  int n, m, i, spar;

  n = fgetint();
  m = fgetint();
  for( i = 0 ; i < m ; i++ ){
    a[i] = fgetint() - 1;
    b[i] = fgetint() - 1;
    good[i] = 1;

    adj[a[i]].push_back( i );
    adj[b[i]].push_back( i );
  }

  spar = 0;
  for( i = 0 ; i < n ; i++ )
    spar += (adj[i].size() & 1);

  if( spar ){
    fputs( "-1\n", fout );
    fclose( fin );
    fclose( fout );
    return 0;
  }

  sp = 0;
  dfs( 0 );

  for( i = 1 ; i < sp ; i++ )
    fprintf( fout, "%d ", cycle[i] + 1 );
  fputc( '\n', fout );

  fclose( fin );
  fclose( fout );
  return 0;
}