Cod sursa(job #1582405)

Utilizator PTAdrian64Pop-Tifrea Adrian PTAdrian64 Data 27 ianuarie 2016 21:36:34
Problema Ciclu Eulerian Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.1 kb
#include <cstdio>
#define nmax 100004
#include <list>
#include <stack>
#include <queue>

using namespace std;

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

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);
   V[x].push_back(y);d[x]++;
   V[y].push_back(x);d[y]++;
 }
 
 Q.push(1);
 viz[1] = true;
 while(!Q.empty()){
   x = Q.front();
   Q.pop();
   for(list <int> :: iterator it = V[x].begin();it != V[x].end();++it)
     if(viz[*it] == false){
       viz[*it] = true;
       Q.push(*it);
     }
 }

 for(i = 1;i <= N;++i)if(d[i]%2 == 1 || viz[i] == false)break;
 if(i<=N)printf("-1/n");
 else{
   x = 1;
   do{
     while(!V[x].empty()){
       y = V[x].front();
       V[x].pop_front();
       for(list <int> :: iterator it = V[y].begin();it != V[y].end();++it)
	 if(*it == x){
           V[y].erase(it);
	   break;
	 }
       S.push(x);
       x = y;
     }
     x = S.top();
     S.pop();
     printf("%d ",x);
   }while(!S.empty());
   printf("\n");
 }
 
 return 0;
}