Cod sursa(job #1127994)

Utilizator roby2001Sirius roby2001 Data 27 februarie 2014 14:41:59
Problema Ciclu Eulerian Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.25 kb
/*
    Keep It Simple!
*/

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

#define MaxN 100005

using namespace std;

list<int> G[MaxN],Queue,E;
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 Ciclu_Euler(int node)
{
    while(G[node].size())
    {
       int aux = G[node].front();
       G[node].pop_front();
       sw = 0;
       for(list<int>::iterator it = G[aux].begin();it!=G[aux].end() && sw == 0;it++)
         if( *it == node )
         {
          G[aux].erase(it); sw = 1;
         }
       Ciclu_Euler(aux);
    }
    E.push_front(node);
}

int main()
{
   freopen("dfs.in","r",stdin);
   freopen("dfs.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);
      printf("\b\b\b ");
    }
    else
    printf("-1");
}