Pagini recente » Cod sursa (job #3279769) | Cod sursa (job #1996305) | Cod sursa (job #188019) | Cod sursa (job #3202553) | Cod sursa (job #2909925)
#include <bits/stdc++.h>
#define ll long long
using namespace std;
ifstream fin("ciclueuler.in");
ofstream fout("ciclueuler.out");
int const N = 2e5 + 5, M = 5e5 + 5;
vector<pair<int, int>> graph[N];
vector<int> cycle;
bitset<M> seen;
stack<int> nodes;
void find_eulerian_cycle() {
nodes.push(1);
while (!nodes.empty()) {
int node = nodes.top();
if (graph[node].size()) {
int dest = graph[node].back().first, num = graph[node].back().second;
graph[node].pop_back();
if (!seen[num]) {
seen[num] = true;
nodes.push(dest);
}
} else {
nodes.pop();
cycle.push_back(node);
}
}
}
int main() {
ios::sync_with_stdio(0), cin.tie(0);
int n, m;
fin >> n >> m;
for (int i = 1; i <= m; ++i) {
int source, dest;
fin >> source >> dest;
graph[source].push_back({dest, i});
graph[dest].push_back({source, i});
}
for (int i = 1; i <= n; ++i) {
if (graph[i].size() % 2) {
fout << -1;
return 0;
}
}
find_eulerian_cycle();
cycle.pop_back();
for (int nr : cycle) {
fout << nr << ' ';
}
return 0;
}