Cod sursa(job #2208189)

Utilizator Radu_FilipescuFilipescu Radu Radu_Filipescu Data 28 mai 2018 16:39:31
Problema Ciclu Eulerian Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.47 kb
#include <fstream>
#include <vector>
#include <deque>

using namespace std;

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

int N,M;

struct nod
{
  vector <int> Ad;
} Graf[100002];

deque <int> Ciclu_euclidian;

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

  int a,b;
  for(int i=1; i<=M; ++i)
  {
    fin>>a>>b;

    Graf[a].Ad.push_back(b);
    Graf[b].Ad.push_back(a);
  }

  fin.close();
}

  /**********************************

    euler (nod v)
    cat timp (v are vecini)
        w = un vecin aleator al lui v
        sterge_muchie (v, w)
        euler (w)
    sfarsit cat timp
    adauga v la ciclu

  **********************************/

void Euclid(int nod)
{
  int w;

  for(int i=0; i<Graf[nod].Ad.size(); ++i)
  {
    w=Graf[nod].Ad[i];

    /// DACA NU E STEARSA
    if(w==-1) continue;

    /// STERGEM ACUM

    Graf[nod].Ad[i]=-1;

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

    Euclid(w);
  }

  Ciclu_euclidian.push_front(nod);
}

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

  Euclid(1);
}

void Print()
{
  while(!Ciclu_euclidian.empty())
  {
    fout<<Ciclu_euclidian.front()<<' ';
    Ciclu_euclidian.pop_front();
  }

  fout.close();
}

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

    return 0;
}