Cod sursa(job #2454363)

Utilizator ShayVincent Cervoni Shay Data 8 septembrie 2019 00:06:57
Problema Ciclu Eulerian Scor 10
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.35 kb
#include <bits/stdc++.h>

const int BUFFER_SIZE = 1 << 17;
const int NMAX = (int)(5e5) + 1;
char buffer[BUFFER_SIZE];
int pos = BUFFER_SIZE, n, m;
bool visited[NMAX];
std::vector<std::pair<int, int>> v[NMAX];

inline char next() {
	if (pos == BUFFER_SIZE) {
		fread(buffer, 1, BUFFER_SIZE, stdin);
		pos = 0;
	}
	
	return buffer[pos++];
}

inline int read() {
	int n = 0;
	char c = next();

	while (!('0' <= c && c <= '9')) {
		c = next();
	}

	while ('0' <= c && c <= '9') {
		n = (n << 3) + (n << 1) + (c - '0');
		c = next();
	}

	return n;
}

inline void print(int n) {
	char snum[7];
	int i = 0;

	do {
		snum[i++] = n % 10 + '0';
		n /= 10;
	} while (n);

	fwrite(snum, i, sizeof(char), stdout);
	putchar(' ');
}

void dfs(int node) {
	while (v[node].size()) {
		int current = v[node].back().first;
		int neighbor = v[node].back().second;
		v[node].pop_back();

		if (!visited[neighbor]) {
			visited[neighbor] = true;
			dfs(current);
		}
	}

	if (m) print(node), --m;
}

int main() {
	freopen("ciclueuler.in", "r", stdin);
	freopen("ciclueuler.out", "w", stdout);
	n = read(), m = read();

	for (int i = 1 ; i <= m ; ++i) {
		int src = read(), dest = read();
		v[src].emplace_back(std::make_pair(dest, i));
		v[dest].emplace_back(std::make_pair(src, i));
	}

	for (int i = 1 ; i <= n ; ++i) {
		if (v[i].size() & 1) {
			printf("-1");
			return 0;
		}
	}

	dfs(1);
	return 0;
}