Cod sursa(job #2696707)

Utilizator andreic06Andrei Calota andreic06 Data 16 ianuarie 2021 13:38:56
Problema Ciclu Eulerian Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.2 kb
#include <iostream>
#include <fstream>
#include <vector>

using namespace std;
const int MAX_MUCHII = 5e5;
const int MAX_N = 1e5;

int from[1 + MAX_MUCHII], to[1 + MAX_MUCHII];
int visited[1 + MAX_MUCHII];
vector<int> muchii[1 + MAX_N];
vector<int> res;

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

bool valid = false;
void euler ( int root ) {

   while ( muchii[root].size () ) {
      int muchia = muchii[root].back ();

      muchii[root].pop_back ();
      if ( visited[muchia] == 0 ) {
        visited[muchia] = 1;

        int nod;
        if ( from[muchia] == root )
          nod = to[muchia];
        else
          nod = from[muchia];
        euler ( nod );
      }
   }

   res.push_back ( root );
}

int main()
{
   int n, m; fin >> n >> m;
   for ( int i = 1; i <= m; i ++ ) {
      fin >> from[i] >> to[i];
      muchii[from[i]].push_back ( i );
      muchii[to[i]].push_back ( i );
   }

   int i = 1;
   while ( i <= n && (int)muchii[i].size () % 2 == 0 )
      i ++;
   if ( i == n + 1 ) {
     euler ( 1 );
     res.pop_back ();
     for ( auto x : res )
        fout << x << ' ';
   }
   else
     fout << -1;
    return 0;
}