Pagini recente » Cod sursa (job #521906) | Cod sursa (job #2125645) | Cod sursa (job #2720319) | Cod sursa (job #856752) | Cod sursa (job #2422854)
#include <fstream>
#include <vector>
#include <bitset>
const int MaxN = 100001;
const int MaxE = 500001;
struct Edge{
int a, b;
};
std::ofstream fout("ciclueuler.out");
using VI = std::vector<int>;
using VVI = std::vector<VI>;
using VE = std::vector<Edge>;
std::bitset<MaxE> v;
VVI G;
VE E;
VI ce;
int n, m;
void ReadData();
bool IsEulerian();
inline void Dfs(int x);
void Write();
int main()
{
ReadData();
if (!IsEulerian())
fout << "-1";
else
{
Dfs(1);
Write();
}
}
void ReadData()
{
std::ifstream fin("ciclueuler.in");
fin >> n >> m;
G = VVI(n + 1);
E = VE(m + 1);
for (int i = 1, a, b; i <= m; ++i)
{
fin >> a >> b;
G[a].emplace_back(i);
G[b].emplace_back(i);
E[i] = {a, b};
}
}
bool IsEulerian()
{
for (int x = 1; x <= n; ++x)
if (G[x].size() % 2 == 1)
return false;
return true;
}
void Dfs(int x)
{
for (const int& e : G[x])
{
if (v[e]) continue;
v[e] = 1;
if (E[e].a == x)
Dfs(E[e].b);
else
Dfs(E[e].a);
}
ce.emplace_back(x);
}
void Write()
{
for (size_t i = 0; i < ce.size() - 1; ++i)
fout << ce[i] << ' ';
}