Cod sursa(job #1496422)

Utilizator elevenstrArina Raileanu elevenstr Data 4 octombrie 2015 22:16:11
Problema Ciclu Eulerian Scor 80
Compilator cpp Status done
Runda Arhiva educationala Marime 1.15 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 dfs(int nod)
{  viz[nod]=1;
   for(vector <int> ::iterator it=v[nod].begin();it!=v[nod].end();it++)
        if(viz[*it]==0)dfs(*it);
}

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]++;
}
dfs(1);
euler();
for(i=1;i<=n;i++)
    if(viz[i]==0||gr[i]%2)
{
    out<<-1;
    return 0;
}
for(i=0;i<sol.size()-1;i++)
out<<sol[i]<<" ";



    return 0;
}