Cod sursa(job #1496424)

Utilizator elevenstrArina Raileanu elevenstr Data 4 octombrie 2015 22:18:17
Problema Ciclu Eulerian Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.98 kb
#include <iostream>
#include <fstream>
#include <stack>
#include <vector>
#include <bitset>
#include <algorithm>
using namespace std;
#define MAX 100070
stack <int> S;
vector <int> v[MAX];
int gr[MAX];
vector <int> sol;
bitset <MAX> viz;
ifstream in("ciclueuler.in");
ofstream out("ciclueuler.out");

inline void euler()
{  S.push(1);
  while(!S.empty())
  {   int nod=S.top();
      if(!v[nod].empty())
      {
          int nou=v[nod].back();
          S.push(nou);
          v[nod].pop_back();
          v[nou].erase(find (v[nou].begin(),v[nou].end(),nod));
      }
      else
      {
          sol.push_back(nod);
          S.pop();
      }
  }

}

int main()
{   int n,m,x,y,i,j;
in>>n>>m;
for(i=1;i<=m;i++)
{
    in>>x>>y;
    v[x].push_back(y);
    v[y].push_back(x);
    gr[x]++;
    gr[y]++;
}

euler();
for(i=1;i<=n;i++)
    if(gr[i]%2)
{
    out<<-1;
    return 0;
}
for(i=0;i<sol.size()-1;i++)
out<<sol[i]<<" ";



    return 0;
}