Cod sursa(job #1219689)

Utilizator pavlov.ionPavlov Ion pavlov.ion Data 14 august 2014 20:25:44
Problema Ciclu Eulerian Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 1.17 kb
#include<fstream>
#include<list>
#include<algorithm>
#include<vector>
#include<queue>
#include<stack>
#define MAXN 100005
#define pb push_back
using namespace std;
ifstream cin("ciclueuler.in");
ofstream cout("ciclueuler.out");
list <int> G[MAXN];
list <int>:: iterator it;
vector <int> ciclu;
queue <int> q;
stack <int> S;
int N,M,deg[MAXN],viz[MAXN];
void read() {
	int x,y,i;
	cin>>N>>M;
	for(i=1;i<=M;i++) {
				   cin>>x>>y;
				   G[x].pb(y); deg[x]++;
				   G[y].pb(x); deg[y]++; }
}
int eulerian() {
	for(int i=1;i<=N;i++)
	   if (deg[i]%2 ) return 0;
return 1;
}
void sterge(int v,int w) {
    deg[v]--; deg[w]--;
    G[v].pop_front();
    for(it=G[w].begin();it!=G[w].end();it++)
                         if(*it==v)  {
                                G[w].erase(it);
								break; }  
}
void euler(int v) {
	 int w;
while(G[v].size()) {
				w=G[v].front();
				sterge(v,w);
				euler(w);    } 
		ciclu.pb(v);		  
}
int main() {
	int i;
	read();
	if (eulerian())  {      
	   		    euler(1);	 
	   			for(i=0;i<ciclu.size()-1;i++)
       	 			      cout<<ciclu[i]<<" ";  }
	 			             
	else cout<<"-1";       
return 0;
}