Cod sursa(job #2345065)

Utilizator Radu_FilipescuFilipescu Radu Radu_Filipescu Data 15 februarie 2019 21:04:21
Problema Ciclu Eulerian Scor 80
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.31 kb
#include <fstream>
#include <vector>
#include <deque>

using namespace std;

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

const int NMAX = 100002;

int N, M;

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

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 Do()
{
  for( int i = 1; i <= N; ++i )
    if( Ad[i].size() % 2 )
    {
      fout << "-1\n";

      return;
    }

  int w, nod;
  bool found;

  deque <int> S;
  S.push_back( 1 );

  while( !S.empty() )
  {
    nod = S.back();
    S.pop_back();

    found = false;

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

      if( w == -1 ) continue;

      S.push_back( nod );
      S.push_back( w );

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

      found = true;
    }

    if( found ) continue;
    else Ciclu.push_back( nod );
  }

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

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

    fout.close();

    return 0;
}