Cod sursa(job #1611959)

Utilizator RadduFMI Dinu Radu Raddu Data 24 februarie 2016 16:52:46
Problema Ciclu Eulerian Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.93 kb
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
ifstream f("ciclueuler.in");
ofstream g("ciclueuler.out");
vector <int> v[100005];
int n,m,a[500005],sol[500005],gr[100005],k,nsol;
void Del(int x,int y)
{ int i,len=v[x].size();

  for(i=0;i<len;i++)
   if (v[x][i]==y)
   { v[x][i]=v[x][len-1];
     v[x].pop_back();
     return;
   }
}


void Euler(int x)
{ int i,k,nod,nod2;
  k=1; a[1]=1;

  while(k)
  { nod=a[k];

    while (v[nod].size())
    { nod2=v[nod][0];
      Del(nod,nod2); Del(nod2,nod);
      nod=nod2;
      k++; a[k]=nod;
    }

   nsol++; sol[nsol]=a[k]; k--;
  }
}

int main()
{ int i,x,y;
   f>>n>>m;
   for(i=1;i<=m;i++)
   { f>>x>>y;
      v[x].push_back(y);
      v[y].push_back(x);
     gr[x]++; gr[y]++;
   }
 for(i=1;i<=n;i++)
 if (gr[i]%2!=0) {g<<"-1"; return 0;}
   Euler(1);

   for(i=1;i<=nsol;i++)
    g<<sol[i]<<" ";
    return 0;
}