Cod sursa(job #399501)

Utilizator BaduBadu Badu Badu Data 20 februarie 2010 16:16:06
Problema Ciclu Eulerian Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.41 kb
#include <fstream>
#include <list>
#include <stack>
#include <queue>
#define max 100005

using namespace std;

list <int> G[ max ],R;
stack<int> St;
queue<int> Q;

int Deg[max];
char viz[max];
int n,m;

void BFS( int nod ) {
	
	Q.push(nod); 
	viz[nod]=1;
	
	while(!Q.empty() ){
		nod = Q.front();
		Q.pop();
		for( typeof(G[nod].begin()) it = G[nod].begin(); it != G[nod].end(); it++)
			if( viz[ *it ] == '0' ){ 
				Q.push( *it );
				viz[ *it ] =1;
			}
	}
}

int not_euler(){
	
	BFS(1);
	int i;
	for(i=1;i<=n;i++) if( viz[i]=='0' ) return 1;
	
	for(i=1;i<=n;i++) if( Deg[i] & 1 ) return 1;
	
	return 0;
}

void Sterge( int v, int w){
	Deg[v]--;Deg[w]--;
	G[v].pop_front();
	for( typeof(G[w].begin()) it=G[w].begin(); it != G[w].end(); it++) 
		if( *it == v ) {G[w].erase(it);break;}
}
	
void solve(){
	int v =1,w;
	do{
		
		while(1){
			if( G[v].empty() ) break;
			w = G[v].front();
			St.push(v);
			Sterge(v,w);
			v = w;
		}
		v = St.top();
		St.pop();
		R.push_back(v);
		
	}while( !St.empty() );
}

int main(){
	
	ifstream f("ciclueuler.in");
	ofstream g("ciclueuler.out");
	
	f>>n>>m;
	int i,x,y;
	for(i=1;i<=m;i++){
		f>>x>>y;
		G[x].push_back(y);Deg[x]++;
		G[y].push_back(x);Deg[y]++;
	}

	if( not_euler() ) { g<<"-1"; return 0; }
	
	solve();
	
	for( typeof( R.begin() ) it=R.begin(); it != R.end(); it++) g<<(*it)<<" ";
	
	return 0;
}