Cod sursa(job #689377)

Utilizator d.andreiDiaconeasa Andrei d.andrei Data 24 februarie 2012 13:59:59
Problema Ciclu Eulerian Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.89 kb
#include <cstdio>
#include <vector>
#include <stack>

using namespace std;

#define file_in "ciclueuler.in"
#define file_out "ciclueuler.out"

#define nmax 101000

int N,M,a,b,i;
vector<int> G[nmax];
stack<int> S;

int main(){
	
	freopen(file_in,"r",stdin);
	freopen(file_out,"w",stdout);
	
	scanf("%d %d", &N, &M);
	while(M--){
		
		scanf("%d %d", &a, &b);
		
		G[a].push_back(b);
		G[b].push_back(a);
	}
	
	
	for (i=1;i<=N;++i)
		if (G[i].size()&1){
			printf("-1\n");
			return 0;
		}
		
	S.push(1);
	while(!S.empty()){
		a=S.top();
		if (G[a].size()>=1){
			b=G[a].back();
			S.push(b);
			//a->b
			G[a].pop_back();
			vector<int> :: iterator it;
			
			for (it=G[b].begin();it!=G[b].end();++it)
				 if (*it==a){
					 G[b].erase(it);
					 break;
				 }
		}
		else{
			S.pop();
			if (!S.empty())
				printf("%d ", a);
		}
	}
	
	return 0;
}