Cod sursa(job #2055298)

Utilizator horiacoolNedelcu Horia Alexandru horiacool Data 3 noiembrie 2017 00:25:44
Problema Ciclu Eulerian Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 1.29 kb
#include <iostream>
#include <fstream>
#include <iterator>
#include <vector>
#include <stack>
using namespace std;
ifstream fin("ciclueuler.in");
ofstream fout("ciclueuler.out");
#define NMAX 100003
int x,y,N,M;

vector<int> v[NMAX];
 stack<int>S,Ssol;

void Delete(int pt,int val)
{
     for(vector<int>::iterator it = v[pt].begin() ; it != v[pt].end() ; ++it)
         if(*it == val)
         {
            v[pt].erase(it);
            break;
         }
}

void Ciclu_Eulerian(int xp)
{
   S.push(xp);
   int n,u = 1;

   while( u != 0 )
   {
      n = S.top();
      vector<int>::iterator it = v[n].begin();
      if( it != v[n].end() )
      {
          u++;
          S.push(*it);
          Delete(*it,n);
          v[n].erase(it);
      }
      else
      {
          u--;
          Ssol.push(S.top());
          S.pop();
      }
   }
}

int main()
{
   fin>>N>>M;
   for(int i = 1 ; i <= M ; i++)
   {
       fin>>x>>y;
       v[x].push_back(y);
       v[y].push_back(x);
   }
   Ciclu_Eulerian(1);

   if( 1 == Ssol.top() )
   {
       fout<<1<<' ';
       while( !Ssol.empty() )
       {
          if( Ssol.top() != 1 )
          fout << Ssol.top() << ' ';
          Ssol.pop();
       }
   }
    else
       fout << -1;
   return 0;
}