Cod sursa(job #723603)

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

long TE[100005] = {0};
long From[500005] = {0};
long To[500005] = {0};
long Taken[500005] = {0};
//set<long> M[100001];
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] += 2;
   TE[b] += 2;
   From[i] = a;
   To[i] = b;
   Taken[i] = 0;
   M[a].insert(i);
   M[b].insert(i);
  }
 vector<long> V;
 stack<long> S;
 queue<long> Q;
 Q.push(1);
 TE[1] |= 1;
 while (Q.empty() == false)
  {
   i = Q.front();
   Q.pop();

   for (set<long>::iterator it = M[i].begin();it != M[i].end();it++)
    {
     if ((TE[To[*it]] & 1) == 0)
       {
        Q.push(To[*it]);
        TE[To[*it]] |= 1;
       }
     if ((TE[From[*it]] & 1) == 0)
       {
        Q.push(From[*it]);
        TE[From[*it]] |= 1;
       }
    }
  }

 for (i = 1;i <= Noduri;i += 1)
  {
   if ((TE[i] & 3) != 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;
}