Cod sursa(job #3286003)

Utilizator drsbosDarius Scripcaru drsbos Data 13 martie 2025 17:32:40
Problema Ciclu Eulerian Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.17 kb
#include <fstream>
#include <stack>
#include <queue>
#include <cmath>
#include <algorithm>
#include <iostream>
#include <set>
#include <cstring>
#include <map>
#include <string>
#include <bitset>
#include <unordered_map>
#include <unordered_set>
#define oo 2000000
#define MOD 1000000007
using namespace std;

ifstream fin("ciclueuler.in");
ofstream fout("ciclueuler.out");
stack<int>st;
vector<pair<int, int>>l[100005];
bitset<500005>used;
vector<int>rez;
int n, x, y, m;

void eul()
{
	st.push(1);
	while (!st.empty())
	{
		int curr = st.top();
		if (!l[curr].empty())
		{
			pair<int, int>muchie = l[curr].back();
			l[curr].pop_back();
			if (!used[muchie.second])
			{
				used[muchie.second] = 1;
				st.push(muchie.first);
			}
		}
		else
		{
			rez.push_back(curr);
			st.pop();
		}
	}
}
int main()
{
	fin >> n >> m;
	for (int i = 1; i <= m; i++)
	{
		fin >> x >> y;
		l[x].push_back({ y,i });
		l[y].push_back({ x,i });
	}
	for (int i = 1; i <= n; i++)
	{
		if (l[i].size() % 2 == 1)
		{
			fout << "-1";
			return 0;
		}
	}
	eul();
	for (int i = 0; i < rez.size()-1; i++)
	{
		fout << rez[i] << " ";
	}
}