Cod sursa(job #2741791)

Utilizator Turturica_DorinTurturica Dorin Turturica_Dorin Data 19 aprilie 2021 09:27:04
Problema Ciclu Eulerian Scor 10
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.94 kb
#include <fstream>
#include <iostream>
#include <queue>
#include <stack>
#include <string>
#include <list>
#include <assert.h>

using namespace std;

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

list<int>G[100005];
stack<int>st;
string s;
int n, m, i, x, y;

int main() {
	fin >> n >> m;
	for (i = 1; i <= m; i++) {
		fin >> x >> y;
		G[x].push_back(y);
		G[y].push_back(x);
	}
	for (i = 1; i <= n; i++) {
		if (G[i].size() % 2 != 0) {
			fout << -1;
			return 0;
		}
	}
	st.push(1);
	while (st.size()) {
		while (G[st.top()].size()) {
			auto nc = G[st.top()].front();
			//erase muchie
			G[st.top()].pop_front();
			auto it = G[nc].begin();
			for (; *it != st.top() && it != G[nc].end(); ++it);
			G[nc].erase(it);

			st.push(nc);
		}
		s += to_string(st.top()) + ' ';
		st.pop();
	}
	s.erase(s.end()-2, s.end());
	if (s.size() / 2 != m) {
		fout << -1;
		return 0;
	}
	fout << s;
}