Cod sursa(job #523439)

Utilizator andreitheo87Teodorescu Andrei-Marius andreitheo87 Data 18 ianuarie 2011 00:35:34
Problema Ciclu Eulerian Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 1.36 kb
#include <fstream>
#include <iostream>
#include <vector>
#include <string>
using namespace std;
struct Node {
	Node* next;
	int val;
	bool used;
	Node(int x) {
		next = 0;
		val = x;
		used = false;
	}
	Node *simetric;
};
Node* lista[100001];
int solu[500000];
int num = 0;

ifstream fin("ciclueuler.in");
ofstream fout("ciclueuler.out");

Node* bagaNod(int x, int y) {
	Node* newNode = new Node(y);
	newNode->next = lista[x];
	lista[x] = newNode;
	return newNode;
}

void find_euler_cycle() {
	int stack[100000], beg = 0, end = 0;
	stack[0] = 0;
	while (beg<=end) {
		int cn = stack[beg++];
		while (lista[cn] && lista[cn]->used) {
			lista[cn] = lista[cn]->next;
		}
		if (lista[cn]) {
			stack[++end] = lista[cn]->val;
			// lista[cn]->used = true; useless
			lista[cn]->simetric->used = true;
			lista[cn] = lista[cn]->next;
		}
		solu[num++] = cn;
	}
}

int main() {
	memset(lista, 0, sizeof(lista));
	int n, m;
	fin >> n >> m;
	for (int i=0; i < m; i++) {
		int x, y;
		fin >> x >> y;
		--x; --y;
		Node* nod1 = bagaNod(x, y);
		Node* nod2 = bagaNod(y, x);
		nod1->simetric = nod2;
		nod2->simetric = nod1;
	}
	find_euler_cycle();
	if (num != m+1 || solu[num-1]!=0) {
		fout << -1 << endl;
		return 0;
	}
	for(int i=0; i<num-1; i++) {
		fout << solu[i] + 1 << " ";
	}
	fout << endl;
	fout.close();
	return 0;
}