Cod sursa(job #527040)

Utilizator andrei.dAndrei Diaconeasa andrei.d Data 30 ianuarie 2011 14:59:52
Problema Ciclu Eulerian Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 1.18 kb
#include <cstdio>
#include <vector>
#include <cstdlib>

using namespace std;

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

#define nmax 501010

int N,M;
int a[nmax];
int b[nmax];
int viz[nmax];
vector<int> G[nmax];
int nr,v[nmax],i;

#define dim 8192
char ax[dim];
int pz;

inline void cit (int &x)
{
	x = 0;
	while (ax[pz] < '0' || ax[pz] > '9')
		if (++pz == dim)
			fread (ax, 1, dim, stdin), pz = 0;

	while (ax[pz] >= '0' && ax[pz] <= '9')
	{
		x = x * 10 + ax[pz] - '0';
		if (++pz == dim)
			fread (ax, 1, dim, stdin), pz = 0;
	}
}


void dfs(int nod){
	
	vector<int> :: iterator it;
	//viz[nod]=1;
	
	for (it=G[nod].begin();it!=G[nod].end();++it)
         if (!viz[*it]){
			 viz[*it]=1;
			 dfs(a[*it]+b[*it]-nod);
		 }
	v[++nr]=nod;	 
}

int main(){
	
	freopen(file_in,"r",stdin);
	freopen(file_out,"w",stdout);
	
	cit(N);
	cit(M);
	
	for (i=1;i<=M;++i){
		
		cit(a[i]);
		cit(b[i]);
		
		G[a[i]].push_back(i);
		G[b[i]].push_back(i);
	}
	nr=0;
	for (i=1;i<=N;++i)
		 if (G[i].size()&1){
			 printf("-1\n");
			 exit(0);
		 }
		 
	dfs(1);
	
	for (i=1;i<=nr;++i) printf("%d ", v[i]);
	
	return 0;
	
}