Cod sursa(job #2869292)

Utilizator alextmAlexandru Toma alextm Data 11 martie 2022 13:47:03
Problema Ciclu Eulerian Scor 50
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.9 kb
#include <bits/stdc++.h>
using namespace std;

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

const int MAXN = 1e5 + 5;
const int MAXEDGES = 5e5 + 5;

int n, m;
vector<pair<int,int>> G[MAXN];
bool viz[MAXEDGES];
vector<int> answer;

inline void dfs(int node) {
	while(!G[node].empty()) {
		int son = G[node].back().first;
		int edge = G[node].back().second;
		G[node].pop_back();
		if(viz[edge] == 0) {
			viz[edge] = 1;
			answer.emplace_back(son);
			dfs(son);
		}
	}
}

bool isPossible() {
	for(int i = 1; i <= n; i++)
		if(G[i].size() % 2 == 1)
			return 0;
	return 1;
}

int main() {
	fin >> n >> m;

	for(int i = 1; i <= m; i++) {
		int u, v;
		fin >> u >> v;
		G[u].emplace_back(v, i);
		G[v].emplace_back(u, i);
	}

	if(!isPossible()) {
		fout << "-1\n";
		return 0;
	}

	dfs(1);

	reverse(answer.begin(), answer.end());
	for(int node : answer)
		fout << node << ' ';
	fout << '\n';

	return 0;
}