Cod sursa(job #2520818)

Utilizator IoanaDraganescuIoana Draganescu IoanaDraganescu Data 9 ianuarie 2020 19:35:49
Problema Ciclu Eulerian Scor 80
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.99 kb
//ignora asta
#include <algorithm>
#include <bitset>
#include <fstream>
#include <stack>
#include <vector>

using namespace std;

const int NMAX = 1e5;

int N, M;
bitset<NMAX + 5> use;
vector<int> G[NMAX + 5];
stack<int> st;

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

void Dfs(int node) {
	use.set(node);
	for (int son : G[node])
		if (!use[son])
			Dfs(son);
}

void Euler(int node) {
	while (!G[node].empty()) {
		st.push(node);
		int other = G[node].back();
		G[node].pop_back();
		G[other].erase(find(G[other].begin(), G[other].end(), node));
		node = other;
	}
}

int main() {
	fin >> N >> M;
	while (M--) {
		int x, y;
		fin >> x >> y;
		G[x].push_back(y);
		G[y].push_back(x);
	}

	Dfs(1);
	for (int i = 1; i <= N; ++i)
		if (!use[i] || G[i].size() & 1) {
			fout << "-1\n";
			return 0;
		}

	int node = 1;
	do {
		Euler(node);
		node = st.top();
		st.pop();
		fout << node << " ";
	} while (!st.empty());
	return 0;
}