Cod sursa(job #2928442)

Utilizator vlad_dimuVlad Dimulescu vlad_dimu Data 22 octombrie 2022 22:05:03
Problema Ciclu Eulerian Scor 80
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.51 kb
#include <cstdio>
#include <ctype.h>
#include <vector>
#include <stack>
#include <algorithm>
#define MAXN 100000
using namespace std;

FILE *fin, *fout;

vector <int> graph[MAXN];

stack <int> cycle;
stack <int> finalCycle;

int readInt() {
  int ch, res = 0;

  while ( isspace( ch = fgetc( fin ) ) );

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

  return res;
}

int main(){
  fin = fopen( "ciclueuler.in", "r" );
  fout = fopen( "ciclueuler.out", "w" );
  int n, m, i, x, y, gradPar, nod, vecin;
  n = readInt(), m = readInt();
  for( i = 0; i < m; i++ ){
    x = readInt(), y = readInt();
    graph[x - 1].push_back(y - 1);
    graph[y - 1].push_back(x - 1);
  }

  gradPar = 1;
  for( i = 0; i < n; i++ )
    if( graph[i].size() % 2 == 1 )
      gradPar = -1;

  if( gradPar == -1 )
    fprintf( fout, "-1\n" );
  else{
    cycle.push(0);

    while( cycle.size() ){
      nod = cycle.top();

      if( graph[nod].size() ){
        vecin = graph[nod].back();

        //stergem muchia
        graph[nod].pop_back();
        graph[vecin].erase( find( graph[vecin].begin(), graph[vecin].end(), nod ) );
        m--;

        cycle.push(vecin);
      }
      else{
        finalCycle.push(nod);
        cycle.pop();
      }
    }

    if( m != 0 )
      fprintf( fout, "-1\n" );
    else{
      while (finalCycle.size()) {
        fprintf( fout, "%d ", finalCycle.top() + 1 );
        finalCycle.pop();
      }
    }
  }
  return 0;
}