Cod sursa(job #2055286)

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

vector<int> v[NMAX];
 deque<int>DQ;

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)
{
   DQ.push_back(xp);
   int n,u = 1;

   while( u != 0 )
   {
      n = DQ.back();
      vector<int>::iterator it = v[n].begin();
      if( it != v[n].end() )
      {
          u++;
          DQ.push_back(*it);
          Delete(*it,n);
          v[n].erase(it);
      }
      else
      {
          u--;
          DQ.push_front(DQ.back());
          DQ.pop_back();
      }
   }
}

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( DQ.front() == DQ.back() )
       while( !DQ.empty() )
       {
          fout << DQ.front() << ' ';
          DQ.pop_front();
       }
    else
       fout << -1;
   return 0;
}