Cod sursa(job #1487226)

Utilizator aimrdlAndrei mrdl aimrdl Data 16 septembrie 2015 15:06:57
Problema Ciclu Eulerian Scor 80
Compilator cpp Status done
Runda Arhiva educationala Marime 1.01 kb
#include <stdio.h>
#include <vector>
#include <stack>
#include <algorithm>

using namespace std;

#define MAX 100005
int N, M;
stack <int> S;
vector <int> C;

typedef struct {
	vector < vector <int> > Edges;
} Graph;

Graph G;

void read () {
	scanf("%d %d", &N, &M);
	
	G.Edges.resize(N+1);
	
	for (int i = 0; i < M; ++i) {
		int x, y;
		scanf("%d %d", &x, &y);
		
		G.Edges[x].push_back(y);
		G.Edges[y].push_back(x);
	}
}

void euler () {
	S.push(1);
	
	do {
		int x = S.top(), aux;
		if (!G.Edges[x].empty()) {
			aux = G.Edges[x].back();
			S.push(aux);
			G.Edges[x].pop_back();
			G.Edges[aux].erase(find(G.Edges[aux].begin(), G.Edges[aux].end(), x));
		} else {
			C.push_back(x);
			S.pop();
		}
	} while (S.size() > 1);
}

int main (void) {	
	freopen("ciclueuler.in", "r", stdin);
	freopen("ciclueuler.out", "w", stdout);
	
	read();
	euler();
	
	if (C.size() == (unsigned int) M) {
		vector <int>::iterator it;
		for (it = C.begin(); it < C.end(); ++it) {
			printf("%d ", *it);
		}
	} else {
		printf("-1");
	}
	
	return 0;
}