Pagini recente » Cod sursa (job #489196) | Cod sursa (job #3336003) | Cod sursa (job #824142) | Cod sursa (job #455162) | Cod sursa (job #3335518)
#include<bits/stdc++.h>
using namespace std;
ifstream fin("ciclueuler.in");
ofstream fout("ciclueuler.out");
int N, M;
// Algoritm de determinare ciclu euler
// muchie noteaza care muchii au fost vizitate
vector<bool> visitedMuchie;
// u si v sunt vectorii de muchi
// (u[i], v[i]) sunt o muchie
vector<int>u;
vector<int>v;
// vecini pastreaza indicele la aceste muchii
vector<vector<int>> vecini;
vector<int>pos;
// in cycle e creat ciclul
vector<int>cycle;
bool allDegreesEven() {
for (int i=1;i<=N;i++)
if (vecini[i].size() % 2 != 0)
return false;
return true;
}
void dfs(int nod) {
// cat timp nod-ul mai are vecini
// pos[nod] e pozitia la care a ramas nod
while (pos[nod] < vecini[nod].size()) {
int current_edge = vecini[nod][pos[nod]++];
if (!visitedMuchie[current_edge]) {
visitedMuchie[current_edge] = true;
dfs( v[current_edge] );
}
}
cycle.push_back(nod);
}
int main() {
fin>>N>>M;
visitedMuchie.assign(M+1, 0);
u.assign(M+1, 0);
v.assign(M+1, 0);
pos.assign(N+1, 0);
vecini.resize(N+1);
for (int i = 1; i <= M; i++) {
fin>>u[i]>>v[i];
vecini[u[i]].push_back(i);
vecini[v[i]].push_back(i);
}
if (allDegreesEven()) {
dfs(1);
for (int i=cycle.size()-1;i>0;i--)
fout<<cycle[i]<<" ";
}
else {
fout<<-1;
}
return 0;
}