Cod sursa(job #1316549)

Utilizator RaduGabriel2012Dinu Radu RaduGabriel2012 Data 13 ianuarie 2015 21:45:11
Problema Ciclu Eulerian Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.39 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
using namespace std;
ifstream f("ciclueuler.in");
ofstream g("ciclueuler.out");
 vector <int> v[100005];
 queue <int> q;
 int n,m,nod=1,gr[100005],st[500005],k,sol[500005],nsol,use[100005],ok=1;

void Del(int x,int y)
 { int i,j;
    for(i=0;i<v[x].size();i++)
      if (v[x][i]==y)
        { v[x][i]=v[x][v[x].size()-1];
          v[x].pop_back();
          break;
        }

 }

 void BFS()
 { int i,x=1;
     q.push(1);
      use[1]=1;
     while(!q.empty())
      {
         x=q.front(); q.pop();

         for(i=0;i<v[x].size();i++)
           if (!use[v[x][i]])
            {q.push(v[x][i]); use[v[x][i]]=1;}
      }

  for(i=1;i<=n;i++)
   if (!use[i]) ok=0;
 }

void Euler(int x)
{ int i,y;
   while(v[x].size())
   {
     y=v[x][0]; k++; st[k]=y;
      Del(x,y);
      Del(y,x);
       x=y;
   }
}

int main()
{ int i,j,x,y;
    f>>n>>m;

    for(i=1;i<=m;i++)
    { f>>x>>y;
        gr[x]++; gr[y]++;
       v[x].push_back(y);
       v[y].push_back(x);
    }

    for(i=1;i<=n;i++)
     if (gr[i]%2!=0) ok=0;

    BFS();

    if (!ok) g<<"-1\n";
      else
       { k=1; st[k]=1;
           while(k)
           {
               Euler(st[k]);
             nsol++; sol[nsol]=st[k]; k--;
           }
       }

 for(i=1;i<nsol;i++)
  g<<sol[i]<<" ";
    return 0;
}