Pagini recente » Borderou de evaluare (job #434615) | Cod sursa (job #2710126)
#include <bits/stdc++.h>
#include <cassert>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using ld = long double;
using pi = pair<int, int>;
using pl = pair<ll, ll>;
using pd = pair<double, double>;
using pld = pair<ld, ld>;
int main()
{
ifstream cin("ciclueuler.in");
ofstream cout("ciclueuler.out");
int N, M;
cin >> N >> M;
vector<vector<int>> edges_of_node(N + 1);
vector<int> edges(M), deg(N + 1);
for (int cur_edge_idx = 0; cur_edge_idx < M; ++cur_edge_idx)
{
int x, y;
cin >> x >> y;
edges[cur_edge_idx] = x ^ y;
edges_of_node[x].emplace_back(cur_edge_idx);
edges_of_node[y].emplace_back(cur_edge_idx);
++deg[x], ++deg[y];
}
bool can_have_Eulerian_cycle{true};
for (int node = 1; node <= N && can_have_Eulerian_cycle; ++node)
{
can_have_Eulerian_cycle &= deg[node] % 2 == 0;
}
if (!can_have_Eulerian_cycle)
{
cout << "-1";
return 0;
}
stack<int> cur_simple_cycle;
vector<int> res;
cur_simple_cycle.emplace(1);
while (!cur_simple_cycle.empty())
{
const int cur_node = cur_simple_cycle.top();
if (edges_of_node[cur_node].empty())
{
cur_simple_cycle.pop();
res.emplace_back(cur_node);
}
else
{
const int edge_idx = edges_of_node[cur_node].back();
edges_of_node[cur_node].pop_back();
if (~edges[edge_idx])
{
const int adj_node = edges[edge_idx] ^ cur_node;
edges[edge_idx] = -1;
cur_simple_cycle.emplace(adj_node);
}
}
}
res.pop_back();
for (const int node : res)
{
cout << node << " ";
}
}