Pagini recente » Cod sursa (job #2045329) | Cod sursa (job #3244359) | Cod sursa (job #1888971) | Cod sursa (job #2264680) | Cod sursa (job #3214525)
#include <iostream>
#include <fstream>
#include <vector>
#include <bitset>
#include <stack>
#include <queue>
#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;
vector<nod> G[NMAX];
stack<nod> s;
bitset<MMAX> viz;
queue<int> ciclu;
void read_data()
{
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});
}
}
bool admits_cycle()
{
for (int i = 1; i <= n; i++)
if (G[i].size() % 2 == 1)
return false;
return true;
}
bool euler()
{
s.push({1, 0});
while (!s.empty())
{
nod c = s.top();
if (!G[c.nod].empty())
{
nod vec = G[c.nod].back();
G[c.nod].pop_back();
if (!viz[vec.muchie])
{
viz[vec.muchie] = true;
s.push(vec);
}
}
else
{
s.pop();
ciclu.push(c.nod);
}
}
}
int main()
{
read_data();
if (!admits_cycle())
{
fout << -1;
return 0;
}
euler();
while (!ciclu.empty())
{
fout << ciclu.front() << " ";
ciclu.pop();
}
return 0;
}