Cod sursa(job #2668052)

Utilizator CosminMorarMorar Cosmin Andrei CosminMorar Data 4 noiembrie 2020 13:37:23
Problema Ciclu Eulerian Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.09 kb
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using ull = unsigned long long;
ifstream fin("ciclueuler.in");
ofstream fout("ciclueuler.out");
int n, m;
vector<pair<int, int>> edges[100100];
vector<int> euler_cycle;
stack<int> order;
bitset<500100> used;

void generate_euler_cycle() {
	order.push(1);
	while (!order.empty()) {
		int act = order.top();
		
		if (edges[act].empty()) {
			euler_cycle.push_back(act);
			order.pop();
			continue;
		}
		
		int to, to_index;
		tie(to, to_index) = edges[act].back();
		edges[act].pop_back();
		
		if (!used[to_index]) {
			order.push(to);
			used[to_index] = true;
		}
	}
}

int main() {
	cin.tie(0);cout.tie(0);
	ios::sync_with_stdio(0);
	fin >> n >> m;
	for (int i = 1; i <= m; i++) {
		int u, v;
		fin >> u >> v;
		edges[u].push_back(make_pair(v, i));
		edges[v].push_back(make_pair(u, i));
	}
	
	for (int i = 1; i <= n; i++)
		if (edges[i].size() % 2 == 1) {
			fout << -1;
			return 0;
		}
		
	generate_euler_cycle();
	
	for (int i = euler_cycle.size() - 1; i >= 1; i--)
		fout << euler_cycle[i] << ' ';
	return 0;
}