Pagini recente » Cod sursa (job #1220524) | Cod sursa (job #1279024) | Cod sursa (job #1561624) | Cod sursa (job #2089613) | Cod sursa (job #2422871)
#include <fstream>
#include <vector>
#include <bitset>
#include <tuple>
#include <stack>
const int MaxN = 100001;
const int MaxE = 500001;
using VI = std::vector<int>;
using VT = std::vector<std::tuple<int, int>>;
using IT = VT::iterator;
using VIT = std::vector<IT>;
using VVT = std::vector<VT>;
std::ofstream fout("ciclueuler.out");
std::bitset<MaxE> v;
VVT G;
VI ce;
int n, m;
void Read();
bool Euler();
void Solve();
void Write();
int main()
{
Read();
if (!Euler())
{
fout << "-1";
}
else
{
Solve();
Write();
}
}
void Read()
{
std::ifstream fin("ciclueuler.in");
fin >> n >> m;
G = VVT(n + 1);
int x = 0, y = 0;
for (int i = 1; i <= m; ++i)
{
fin >> x >> y;
G[x].emplace_back(y, i);
G[y].emplace_back(x, i);
}
}
bool Euler()
{
for (int x = 1; x <= n; ++x)
{
if (G[x].size() % 2 == 1) return false;
}
return true;
}
void Solve()
{
VIT p = VIT(n + 1);
for (int i = 1; i <= n; ++i)
{
p[i] = G[i].begin();
}
int x = 0, y = 0, e = 0;
std::stack<int> stk;
stk.push(1);
while (!stk.empty())
{
x = stk.top();
if (p[x] == G[x].end())
{
ce.emplace_back(x);
stk.pop();
}
else
{
while (p[x] != G[x].end())
{
std::tie(y, e) = *p[x]++;
if (v[e]) continue;
v[e] = 1;
stk.push(y);
break;
}
}
}
}
void Write()
{
for (size_t i = 0; i < ce.size() - 1; ++i)
fout << ce[i] << ' ';
}