Cod sursa(job #373292)

Utilizator savimSerban Andrei Stan savim Data 13 decembrie 2009 12:57:36
Problema Ciclu Eulerian Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 0.94 kb
#include <stdio.h>
#include <vector>

using namespace std;

#define MAX_N 100010
#define MAX_M 500010

#define pb push_back

vector <int> v[MAX_N], poz[MAX_N];
int n, m, p, q;
int ind[MAX_N], L[MAX_N], grad[MAX_N];
int use[MAX_M], Q[MAX_M];

void cit() {
	freopen("ciclueuler.in", "r", stdin);
	freopen("ciclueuler.out", "w", stdout);

	scanf("%d %d", &n, &m);
	for (int i = 1; i <= m; i++) {
    	scanf("%d %d", &p, &q);
		v[p].pb(q); v[q].pb(p);
		poz[p].pb(i); poz[q].pb(i);

		L[p]++; L[q]++;
		grad[p]++; grad[q]++;
	}
}

void solve(int nod) {
	for (; ind[nod] < L[nod]; ind[nod]++) 
		if (use[poz[nod][ind[nod]]] == 0) {
        	use[poz[nod][ind[nod]]] = 1;
			solve(v[nod][ind[nod]]);
		}

	Q[++Q[0]] = nod;
}

void write() {
	for (int i = 1; i < Q[0]; i++)
		printf("%d ", Q[i]);
	printf("\n");
}

int main() {

	cit();
	
	for (int i = 1; i <= n; i++)
		if (grad[i] % 2) {
        	printf("-1\n");
			return 0;
		}

	solve(1);
	write();

	return 0;
}