Cod sursa(job #2910741)

Utilizator mircea_007Mircea Rebengiuc mircea_007 Data 24 iunie 2022 20:46:37
Problema Ciclu Eulerian Scor 80
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.8 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];
int 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;
}

class ReadOnSteroids {

#define BUFSIZE (128 * 1024)

protected:
  char ibuf[BUFSIZE];
  int ibp;
  FILE *fin;

public:
  inline ReadOnSteroids( char *fname ){
    if( fname )
      fin = fopen( fname, "r" );
    else
      fin = stdin;

    ibp = BUFSIZE - 1;
  }

  inline ~ReadOnSteroids(){
    if( fin != stdin )
      fclose( fin );
  }

  inline char getc(){
    if( (ibp = (ibp + 1) & (BUFSIZE - 1)) == 0 )
      fread( ibuf, sizeof( char ), BUFSIZE, fin );
    return ibuf[ibp];
  }

  template<typename T> inline T get(){
    T n = 0;
    char ch;

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

    return n;
  }

#undef BUFSIZE

};

#define fgetint fin.get<int>

int main(){
  ReadOnSteroids fin( (char *)"ciclueuler.in" );
  FILE *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( fout );
    return 0;
  }

  sp = 0;
  dfs( 0 );

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

  fclose( fout );
  return 0;
}