Cod sursa(job #2575853)

Utilizator dragossofiaSofia Dragos dragossofia Data 6 martie 2020 15:50:42
Problema Ciclu Eulerian Scor 80
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.08 kb
#include <bits/stdc++.h>
#define Nmax 100009

using namespace std;

ifstream fin ("ciclueuler.in");
ofstream fout("ciclueuler.out");

vector < pair < int , int > > ad[Nmax]  ;
vector <int>  sol;
stack <int> S ;
int n,m , viz [ 5*Nmax ];
void read()
{
 fin >> n >> m;
 int x , y ;
 for( int i = 1 ; i<= m ; i ++)
 {
   fin>>x>>y;
   ad[ x ] . push_back( {y , i} );
   ad[ y ] . push_back( {x , i} );
 }

}

void euler ( int nod )
{
  int w,used;
  for( int i = 0 ; i < ad[ nod ].size() ; i ++ )
  {
   w=ad[ nod ][ i ].first;
   used = viz[ ad[ nod ][ i ].second ] ;
   if( used == 0 )
        {
         viz[ ad[ nod ][ i ].second ]= 1 ;
         ad[ nod ].erase( ad[ nod ].begin() + i );
         euler( w );
        }

  }
  sol.push_back( nod );
}

int main()
{
    read();
    for( int i = 1 ; i <= n ; i ++ )
        if( ad[ i ].size() % 2 == 1 )
            {
             fout<<-1;
             return 0;
            }
    euler( 1 );
    for( int i = 0 ; i < sol.size() - 1 ; i ++ )
    {
     fout<<sol[i]<<" ";
    }
    return 0;
}