Cod sursa(job #2055302)

Utilizator horiacoolNedelcu Horia Alexandru horiacool Data 3 noiembrie 2017 00:37:37
Problema Ciclu Eulerian Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 1.31 kb
#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() )
    {
        DQ.pop_back();
        while( !DQ.empty() )
        {
           fout << DQ.front() << ' ';
           DQ.pop_front();
        }
    }
    else
        fout << -1;
    return 0;
}