Cod sursa(job #1564149)

Utilizator PTAdrian64Pop-Tifrea Adrian PTAdrian64 Data 8 ianuarie 2016 17:54:36
Problema Ciclu Eulerian Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.22 kb
#include <cstdio>
#include <list>
#define nmax 100004
#include <stack>
#include <queue>

using namespace std;

int N,M;
bool viz[nmax];
int d[nmax];
list <int> G[nmax];
queue <int> Q;
stack <int> S;

void BFS(){
  viz[1] = true;
  Q.push(1);
  int x;
  while(!Q.empty()){
    x = Q.front();
    Q.pop();
    for(list <int> :: iterator it = G[x].begin();it != G[x].end();++it)
      if(viz[*it] == false){
        viz[*it] = true;
        Q.push(*it);
      }
  }
}

void Losung(){
   int i,j,k;
   BFS();
   for(i = 1;i <= N;++i)
      if(viz[i] == false || d[i]%2 == 1){printf("-1\n");return;}

   i = 1;
   do{
     while(!G[i].empty()){
        j = G[i].front();
        G[i].pop_front();
        for(list <int> :: iterator it = G[j].begin();it != G[j].end();++it)
          if(*it == i){
            G[j].erase(it);
            break;
          }
        S.push(i);
        i = j;
     }
     i = S.top();
     S.pop();
     printf("%d ",i);
   }while(!S.empty());
   printf("\n");
}

int main(){

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

  scanf("%d %d ",&N,&M);
  int x,y;
  while(M--){
    scanf("%d %d ",&x,&y);
    G[x].push_back(y);d[x]++;
    G[y].push_back(x);d[y]++;
  }

  Losung();
  return 0;
}