Cod sursa(job #723598)

Utilizator XladhenianGrigorita Vlad-Stefan Xladhenian Data 25 martie 2012 17:35:44
Problema Ciclu Eulerian Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 1.29 kb
                                                     
#include <fstream>
#include <set>
#include <stack>
#include <vector>
using namespace std;

long TE[100005] = {0};
long From[500005] = {0};
long To[500005] = {0};
long Taken[500005] = {0};
set<long> *M;

int main(void)
{
 fstream fin("ciclueuler.in",ios::in);
 fstream fout("ciclueuler.out",ios::out);
 long Noduri,Muchii,i,a,b;
 M = new set<long>[100001];
 fin >> Noduri >> Muchii;

 for (i = 0;i < Muchii;i += 1)
  {
   fin >> a >> b;
   TE[a] += 1;
   TE[b] += 1;
   From[i] = a;
   To[i] = b;
   Taken[i] = 0;
   M[a].insert(i);
   M[b].insert(i);
  }
 vector<long> V;
 stack<long> S;

 for (i = 0;i < Noduri;i += 1)
  {
   if ((TE[i] & 1) == 1)
     {
      fout << "-1";
      fin.close();
      fout.close();
      return 0;
     }
  }

 S.push(1);
 while (S.empty() == false)
  {
   a = S.top();
   if (M[a].empty() == true)
     {
      V.push_back(a);
      S.pop();
      continue;
     }
   i = *M[a].begin();
   M[To[i]].erase(i);
   M[From[i]].erase(i);
   if (From[i] == a)
     {
      S.push(To[i]);
     }
    else
     {
      S.push(From[i]);
     }
  }
 for (i = (V.size() - 1);i > 0;i -= 1)
  {
   fout << V[i] << " ";
  }
 fin.close();
 fout.close();
 return 0;
}