Pagini recente » Cod sursa (job #372858) | Cod sursa (job #172086) | Cod sursa (job #3174780) | Cod sursa (job #1787858) | Cod sursa (job #2422868)
#include <fstream>
#include <vector>
#include <bitset>
#include <tuple>
#include <stack>
const int MaxN = 100001;
const int MaxE = 500001;
std::ofstream fout("ciclueuler.out");
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::bitset<MaxE> v;
VVT G;
VI ce;
int n, m;
void ReadData();
bool IsEulerian();
void DetCicle(int x);
void Write();
int main()
{
ReadData();
if (!IsEulerian())
fout << "-1";
else
{
DetCicle(1);
Write();
}
}
void ReadData()
{
std::ifstream fin("ciclueuler.in");
fin >> n >> m;
G = VVT(n + 1);
for (int i = 1, a, b; i <= m; ++i)
{
fin >> a >> b;
G[a].emplace_back(b, i);
G[b].emplace_back(a, i);
}
}
bool IsEulerian()
{
for (int x = 1; x <= n; ++x)
if (G[x].size() % 2 == 1)
return false;
return true;
}
void DetCicle(int x)
{
VIT p = VIT(n + 1);
for (int i = 1; i <= n; ++i)
p[i] = G[i].begin();
int y, e;
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()
{
//fout << ce.size() << '\n';
for (size_t i = 0; i < ce.size() - 1; ++i)
fout << ce[i] << ' ';
}