Cod sursa(job #1258189)

Utilizator robertstrecheStreche Robert robertstreche Data 8 noiembrie 2014 16:21:49
Problema Ciclu Eulerian Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.05 kb
#include <fstream>
#include <vector>
#include <algorithm>
#include <stack>

#define lmax 100005
#define pb push_back

using namespace std;

ifstream f("ciclueuler.in");
ofstream g("ciclueuler.out");

int n,m;

stack <int>q;

vector <int>sol,v[lmax];

inline void euler()
{
    q.push(1);

    while (q.size())
     {
         int nod=q.top();

         if (v[nod].size())
          {
              int urm=v[nod].back();
              v[nod].pop_back();
              v[urm].erase(find(v[urm].begin(),v[urm].end(),nod));

              q.push(urm);
          }
         else
          {
              sol.pb(nod);
              q.pop();
          }
     }
}

int main()
{
    int x,y,i;

    f>>n>>m;

    for (i=1;i<=m;i++)
     {
         f>>x>>y;

         v[x].pb(y);
         v[y].pb(x);

     }

    for (i=1;i<=n;i++)
     if (v[i].size()%2)
      {
          g<<-1;
          return 0;
      }

    euler();

    for (i=0;i<sol.size();i++)
     g<<sol[i]<<" ";

    f.close();
    g.close();
}