Cod sursa(job #2345053)

Utilizator Radu_FilipescuFilipescu Radu Radu_Filipescu Data 15 februarie 2019 20:37:57
Problema Ciclu Eulerian Scor 80
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.05 kb
#include <fstream>
#include <vector>

using namespace std;

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

const int NMAX = 100002;

int N, M;

vector <int> Ad[NMAX];
vector <int> S;

int printate;

void Read()
{
  fin >> N >> M;

  int x, y;

  for( int i = 1; i <= M; ++i )
  {
    fin >> x >> y;

    Ad[x].push_back( y );
    Ad[y].push_back( x );
  }

  fin.close();
}

void Euler( int nod )
{
  int w;

  while( !Ad[nod].empty() )
  {
    w = Ad[nod].back();
    Ad[nod].pop_back();

    if( w == -1 ) continue;

    for( int i = 0; i < Ad[w].size(); ++i )
      if( Ad[w][i] == nod )
      {
        Ad[w][i] = -1;
        break;
      }

    Euler( w );
  }

  S.push_back( nod );
}

void Do()
{
  for( int i = 1; i <= N; ++i )
    if( Ad[i].size() % 2 )
    {
      fout << "-1\n";

      return;
    }

  Euler( 1 );

  for( int i = 0; i < S.size() - 1; ++i )
    fout << S[i] << ' ';
}

int main()
{
    Read();
    Do();

    fout.close();

    return 0;
}