Cod sursa(job #1219612)

Utilizator pavlov.ionPavlov Ion pavlov.ion Data 14 august 2014 17:47:12
Problema Ciclu Eulerian Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 1.63 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]++; }
}
void BFS() {
	int x; 
	q.push(1);
	while(!q.empty()) {
			x=q.front();
			q.pop();		                     
	        viz[x]=1;
   for(it=G[x].begin();it!=G[x].end();it++)
                   if(!viz[*it]) 
				                 q.push(*it);
    }							  
}
int eulerian() {
	BFS();
	for(int i=1;i<=N;i++)
	   if (!viz[i] || 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) {
   while( true ) {
        if( G[v].empty() )
                       break;
        int w = G[v].front();
        S.push(v);
        sterge(v,w);
        v=w;
    }
}
void iterativ(int v) {
	   do {
        euler(v);
        v=S.top(); S.pop();
        ciclu.pb(v);
    } while(!S.empty());
}
int main() {
	int i;
	read();
	if (eulerian())  {
	   			iterativ(1);	 
	   			for(i=ciclu.size()-1;i>=0;i--)
	 			             cout<<ciclu[i]<<" ";  }
	 			             
	else cout<<"-1";       
return 0;
}