Cod sursa(job #1128038)

Utilizator Sirius2001Happy Birthday Sirius2001 Data 27 februarie 2014 15:00:44
Problema Ciclu Eulerian Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.37 kb
/*
    Keep It Simple!
*/

#include<stdio.h>
#include<list>

#define MaxN 100008

using namespace std;

list<int> G[MaxN],Queue,E,S;
int n,m;
bool viz[MaxN];

void DFS(int node)
{
   viz[node] = 1;
   for(list<int>::iterator it = G[node].begin(); it!=G[node].end();it++)
     if(!viz[*it])
      DFS(*it);
}

int E_Euler()
{
   for(int i=1;i<=n;i++)
     if(G[i].size()%2)
       return 0;
    DFS(1);
    for(int i=1;i<=n;i++)
       if(viz[i] == 0)
        return 0;
    return 1;
}
int sw;
void DeleteRoad(int a,int b)
{
   G[a].pop_front();
   for(list<int>::iterator it = G[b].begin();it!=G[b].end();it++)
         if( *it == a )
         {
          G[b].erase(it); break;
         }
}
void Ciclu_Euler(int node)
{
    do
    {
      while(G[node].size())
      {
         int aux = G[node].front();
         DeleteRoad(node,aux);
         S.push_back(node);
         node = aux;
      }
      node = S.back();
      S.pop_back();
      E.push_front(node);
    }while(S.size());
}

int main()
{
   freopen("ciclueuler.in","r",stdin);
   freopen("ciclueuler.out","w",stdout);

   scanf("%d%d",&n,&m);

   int x,y;

   for(int i=1;i<=m;i++)
   {
      scanf("%d%d",&x,&y);
      G[x].push_back(y);
      G[y].push_back(x);
   }
    if(E_Euler())
    {
      Ciclu_Euler(1);
      for(list<int>::iterator it=E.begin(); it!=E.end();it++)
      printf("%d ",*it);
    }
    else
    printf("-1");
}