Pagini recente » Cod sursa (job #544362) | Cod sursa (job #2385085) | Cod sursa (job #676152) | Cod sursa (job #139692) | Cod sursa (job #3197669)
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <stack>
#define NMAX 100002
#define MMAX 500002
using namespace std;
ifstream fin ("ciclueuler.in");
ofstream fout ("ciclueuler.out");
struct nod {
int nod, muchie;
};
int n, m, viz[MMAX];
vector<nod> G[NMAX];
stack<nod> s;
queue<int> ciclu;
int are_ciclu_euler()
{
for (int i = 1; i <= n; i++)
if (G[i].size() % 2 == 1)
return 0;
return 1;
}
void euler()
{
s.push({1, 0});
while (!s.empty())
{
nod v = s.top();
if (!G[v.nod].empty())
{
nod w = G[v.nod].back();
G[v.nod].pop_back(); // stergem muchia
if (!viz[w.muchie])
{
viz[w.muchie] = 1;
s.push(w);
}
}
else
{
s.pop();
ciclu.push(v.nod);
}
}
}
int main()
{
fin >> n >> m;
for (int i = 1; i <= m; i++)
{
int x, y;
fin >> x >> y;
G[x].push_back({y, i});
G[y].push_back({x, i});
}
if (!are_ciclu_euler())
{
fout << -1;
return 0;
}
euler();
while (ciclu.size() > 1)
{
fout << ciclu.front() << " ";
ciclu.pop();
}
return 0;
}