Pagini recente » Cod sursa (job #879320) | Cod sursa (job #1745449) | Cod sursa (job #1854299) | Cod sursa (job #341734) | Cod sursa (job #3005354)
#include <fstream>
#include <utility>
#include <vector>
#include <tuple>
#include <stack>
using namespace std;
typedef vector<int> VI;
typedef pair<int, int> PI;
typedef vector<PI> VP;
typedef vector<VP> VVP;
typedef vector<bool> VB;
typedef VP::iterator Iter;
ifstream fin("ciclueuler.in");
ofstream fout("ciclueuler.in");
VVP G;
VB v;
VI ce;
int n, m;
void CitesteDate();
void CicluEuler(int x);
bool EsteEulerian();
void ScrieCiclu();
int main()
{
if (!EsteEulerian())
fout << -1;
else
{
CicluEuler(1);
ScrieCiclu();
}
return 0;
}
void CicluEuler(int x)
{
vector<Iter> p(n + 1);
for (int nod = 1; nod <= n; ++nod)
p[nod] = G[nod].begin();
stack<int> stk;
stk.push(x);
int y, e;
while (!stk.empty())
{
x = stk.top();
if (p[x] == G[x].end())
{
ce.emplace_back(x);
stk.pop();
}
else
{
tie(e, y) = *p[x]++;
if (v[e]) continue;
v[e] = true;
stk.push(y);
}
}
}
void CitesteDate()
{
fin >> n >> m;
G = VVP(n + 1);
v = VB(m + 1);
int x, y;
for (int i = 1; i <= m; ++i)
{
fin >> x >> y;
G[x].emplace_back(i, y);
G[y].emplace_back(i, x);
}
}
void ScrieCiclu()
{
for (int x : ce)
fout << x << ' ';
}
bool EsteEulerian()
{
for (int x = 1; x <= n; ++x)
if (G[x].size() % 2 == 1)
return false;
return true;
}