Pagini recente » Istoria paginii runda/nopainnogain | Cod sursa (job #1805143) | Cod sursa (job #733730) | Cod sursa (job #934650) | Cod sursa (job #1482023)
#include <bits/stdc++.h>
using namespace std;
typedef int var;
ifstream fin("ciclueuler.in");
ofstream fout("ciclueuler.out");
#define MAXN 100005
vector<pair<int, int>> G[MAXN];
bool Viz[MAXN];
int Parent[MAXN];
bool Del[1000000];
void dfs(int node) {
Viz[node] = 1;
for(auto &e : G[node]) {
if(!Viz[e.first]) {
Parent[e.first] = node;
Del[e.second] = 1;
dfs(e.first);
}
}
}
vector<int> Ciclu;
void ciclu(int node) {
while(node != 0) {
Ciclu.push_back(node);
while(!G[node].empty() && Del[G[node].back().second])
G[node].pop_back();
if(G[node].empty()) {
node = Parent[node];
} else {
Del[G[node].back().second] = 1;
node = G[node].back().first;
G[node].pop_back();
}
}
Ciclu.pop_back();
}
int main() {
int m, n, a, b;
fin>>n>>m;
while(m--) {
fin>>a>>b;
G[a].push_back({b, m});
G[b].push_back({a, m});
}
dfs(1);
for(int i=1; i<=n; i++) {
if(!Viz[i] || G[i].size() % 2) {
fout<<"-1";
return 0;
}
}
ciclu(1);
for(auto i : Ciclu) fout<<i<<" ";
return 0;
}