Pagini recente » Cod sursa (job #2155401) | Cod sursa (job #3353634) | Cod sursa (job #742346) | Monitorul de evaluare | Cod sursa (job #3330719)
#include <bits/stdc++.h>
#include <fstream>
using namespace std;
int n, m;
vector<pair<int, int>> G[100001];
bool viz[500001];
ifstream f("ciclueuler.in");
ofstream g("ciclueuler.out");
void ReadInput() {
f >> n >> m;
for (int i = 1; i <= m; i++) {
int x, y;
f >> x >> y;
G[x].push_back({y, i});
G[y].push_back({x, i});
}
}
vector<int> ciclu;
void dfs(int nod) {
while (G[nod].size() > 0) {
auto it = G[nod].back();
G[nod].pop_back();
int vecin = it.first;
int id_muchie = it.second;
if (viz[id_muchie])
continue;
viz[id_muchie] = 1;
dfs(vecin);
ciclu.push_back(vecin);
}
}
void FindEulerianCycle() {
for (int i = 1; i <= m; i++)
viz[i] = 0;
dfs(1);
for (int i = 1; i <= m; i++)
if (!viz[i]) {
g << "-1\n";
return;
}
reverse(ciclu.begin(), ciclu.end());
for (auto x : ciclu)
g << x << " ";
}
int main() {
ReadInput();
bool ok = 1;
for (int i = 1; i <= n; i++)
if (G[i].size() % 2 != 0) {
ok = 0;
break;
}
if (ok)
FindEulerianCycle();
else
g << "-1\n";
return 0;
}