Pagini recente » Cod sursa (job #160125) | Cod sursa (job #965543) | Cod sursa (job #1708274) | Cod sursa (job #373) | Cod sursa (job #1481866)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("ciclueuler.in");
ofstream fout("ciclueuler.out");
#define MAXN 100005
int n, m, cnt;
unordered_multiset<int> G[MAXN];
vector<int> ciclu;
vector<bool> used;
void dfs1(int node){
used[node]=1;
cnt++;
for(auto vec : G[node])
if(!used[vec])
dfs1(vec);
}
bool euler(){
used.resize(n+1, 0);
for(int i=1; i<=n; i++)
if(G[i].size() % 2)
return false;
dfs1(1);
if(cnt<n)
return false;
return true;
}
void dfs2(int node){
while(!G[node].empty()){
auto it1 = G[node].begin();
int vec = *it1;
G[node].erase(it1);
auto it2 = G[vec].find(node);
G[vec].erase(it2);
dfs2(vec);
}
ciclu.push_back(node);
}
int main()
{
int x, y;
fin>>n>>m;
while(m--){
fin>>x>>y;
G[x].insert(y);
G[y].insert(x);
}
if(euler()==false){
fout<<"-1";
return 0;
}
dfs2(1);
ciclu.pop_back();
for(auto p : ciclu)
fout<<p<<" ";
return 0;
}