Cod sursa(job #2692548)

Utilizator mex7Alexandru Valentin mex7 Data 3 ianuarie 2021 00:09:59
Problema Ciclu Eulerian Scor 80
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.22 kb
#include <bits/stdc++.h>
#define ll long long
#define cin fin
#define cout fout
using namespace std;
	
ifstream fin("ciclueuler.in");
ofstream fout("ciclueuler.out");
int n, m, x, y;
vector <int> adj[100004];
 
void del(int toDel, vector <int> &from) {
	for (int i = 0; i < from.size(); i++)
		if (from[i] == toDel) {
			for (int j = i; j < from.size() - 1; j++) 
				from[j] = from[j + 1];
			from.pop_back();
			return;
		}	
}

int main() {
	cin >> n >> m;
	for (int i = 1; i <= m; i++) {
		cin >> x >> y;
		adj[x].push_back(y);
		adj[y].push_back(x);
	}

	for (int i = 1; i <= n; i++) 
		if (!adj[i].empty() && adj[i].size() % 2) {
			cout << -1;
			return 0;
		}


	// for (int i = 1; i <= n; i++) {
	// 	cout << i << ": ";
	// 	for (int x : adj[i])
	// 		cout << x << ' ';
	// 	cout << "\n";
	// }

	stack <int> currNode;
	vector <int> result;
	currNode.push(1);
	while (!currNode.empty()) {
		int node = currNode.top();

		if (adj[node].empty()) {
			result.push_back(node);
			currNode.pop();
		} else {
			int nextNode = adj[node][0];
		
			del(nextNode, adj[node]);
			del(node, adj[nextNode]);
			

			currNode.push(nextNode);
		}
	}

	for (int i = 0; i < result.size() - 1; i++)
		cout << result[i] << ' ';

	return 0;
} //1 2 2 3 4 3