Cod sursa(job #272618)

Utilizator toni2007Pripoae Teodor Anton toni2007 Data 7 martie 2009 15:30:03
Problema Ciclu Eulerian Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.82 kb
#include <cstdio>
#include <vector>

using namespace std;

#define maxN 100100
#define maxM 500100

int viz[maxM], grad[maxN], N, M;
vector<int> Cine[maxN], NrM[maxN], Sol;

void df(int nod) {
	int i; Sol.push_back(nod);
	for (i = 0; i < Cine[nod].size(); ++ i)
		if (!viz[NrM[nod][i]]){
			viz[NrM[nod][i]] = 1;
			df(Cine[nod][i]);
		}
}
int main() {
	int i, a, b;
	freopen("ciclueuler.in", "r", stdin);
	freopen("ciclueuler.out", "w", stdout);
	
	scanf("%d%d", &N, &M);
	
	for (i = 1; i <= M; ++ i){
		scanf("%d%d", &a, &b);
		++ grad[a];
		++ grad[b];
		Cine[a].push_back(b);
		Cine[b].push_back(a);
		NrM[a].push_back(i);
		NrM[b].push_back(i);
	}
	for (i = 1; i <= N; ++ i)		if (grad[i] & 1) {	printf("-1\n");		return 0;	}
	
	for (i = 1; i <= N && !grad[i]; ++ i);
	df(i);
	
	for (i = 0; i < Sol.size(); ++ i)	printf("%d ", Sol[i]);
}