Cod sursa(job #2910747)

Utilizator mircea_007Mircea Rebengiuc mircea_007 Data 24 iunie 2022 21:15:49
Problema Ciclu Eulerian Scor 80
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.59 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;
}

class ReadOnSteroids{char i[131072];int I=131071;FILE *f;public:ReadOnSteroids(char*g){f=fopen(g,"r");}~ReadOnSteroids(){fclose(f);}inline char getc(){if(!(I=(I+1)&131071))fread(i,sizeof(char),131072,f);return i[I];}template<typename T>T get(){T n=0;char c;while(!isdigit(c=fgetc(f)));do n=n*10+c-48;while(isdigit(c=fgetc(f)));return n;}};

#define fgetint fin.get<int>

FILE *fout;

void fputint( int n ){
  char out[] = "000000 ";
  int i = 6;

  while( n ){
    out[--i] = '0' + n % 10;
    n /= 10;
  }

  fputs( out + i, fout );
}

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