Pagini recente » Cod sursa (job #2140087) | Cod sursa (job #1881619) | Cod sursa (job #2827741) | Borderou de evaluare (job #1569088) | Cod sursa (job #3230179)
#include <fstream>
#include <vector>
using namespace std;
const int Nmax = 100001;
const int Mmax = 500001;
int n, m, st[Mmax], dr[Mmax], sol[Nmax];
bool viz[Nmax], vizEuler[Mmax];
vector<int> L[Nmax];
void dfs(int nod){
viz[nod] = true;
for(int edge : L[nod]){
int nextNode = st[edge] + dr[edge] - nod;
if(!viz[nextNode]){
dfs(nextNode);
}
}
}
bool conex(){
dfs(1);
for(int i = 1; i <= n; i++){
if(!viz[i])
return false;
}
return true;
}
bool euler(){
if(!conex())
return false;
for(int i = 1; i <= n; i++){
if(L[i].size() & 1)
return false;
}
return true;
}
void dfsEuler(int nod){
while(!L[nod].empty()){
int edge = L[nod].back();
L[nod].pop_back();
if(!vizEuler[edge]){
vizEuler[edge] = true;
dfsEuler(st[edge] + dr[edge] - nod);
}
}
sol[++sol[0]] = nod;
}
int main(){
ifstream fin("ciclueuler.in");
ofstream fout("ciclueuler.out");
fin >> n >> m;
for(int i = 1; i <= m; i++){
fin >> st[i] >> dr[i];
L[st[i]].push_back(i);
L[dr[i]].push_back(i);
}
if(!euler()){
fout << -1;
}
else{
dfsEuler(1);
for(int i = sol[0]; i > 1; --i){
fout << sol[i] << " ";
}
}
return 0;
}