Cod sursa(job #394491)

Utilizator APOCALYPTODragos APOCALYPTO Data 11 februarie 2010 00:09:05
Problema Ciclu Eulerian Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.56 kb
#include<iostream>
#include<fstream>
#include<stdio.h>
#include<vector>
#include<queue>
#include<list>
using namespace std;
#define foreach(v) for(typeof (v).begin() it=(v).begin();it!=(v).end();it++)

queue<int> q;
vector<int> G[100010];
vector<int> La;
int viz[100010]={0};
vector<int> stack;
int n,m;


ofstream fout("ciclueuler.out");
void  bfs()
{int u;
q.push(1);
viz[1]=1;
while(!q.empty())
  {u=q.front();
  q.pop();

  foreach(G[u])
  if(viz[*it]==0)
  { q.push(*it);
  viz[*it]=1;
  }
  }
}




int verif()
{int i;
for( i=1;i<=n;i++)
   if(G[i].size()%2!=0)
      return 0;
 bfs();
 for(i=1;i<=n;i++)
  if(viz[i]==0)
   return 0;
 return 1;
}

void sterge(int v,int w)
{G[v].erase(G[v].begin());
foreach(G[w])
 {if(*it==v)
  G[w].erase(it);
  break;
 }
}

void euler(int v)
{
    while(!G[v].empty())
    {int w=G[v].front();
    stack.push_back(w);
    sterge(v,w);
    v=w;
    }
}


void rez(int x)
{int v;
    if(!x)
    fout<<-1;
    else
    {v=1;
    stack.push_back(v);
    while(!stack.empty())
    {v=stack.back();

    euler(v);
    stack.pop_back();
    La.push_back(v);
    }

    foreach(La)
       fout<<*it<<" ";

    }
}




int main()
{int alfa,beta,i;
    ifstream fin("ciclueuler.in");
    fin>>n>>m;
    for(i=1;i<=m;i++)
      {fin>>alfa>>beta;
      G[alfa].push_back(beta);
      G[beta].push_back(alfa);
      }
    fin.close();
    rez(verif());
    fout.close();
    return 0;
}