Pagini recente » Cod sursa (job #1373335) | Cod sursa (job #629759) | Cod sursa (job #1232010) | Cod sursa (job #433133) | Cod sursa (job #1111605)
#include <cstdio>
#include <stack>
#include <vector>
#include <queue>
#define FILEIN "ciclueuler.in"
#define FILEOUT "ciclueuler.out"
#define NMAX 100002
using namespace std;
vector<int> A[NMAX];
bool Uz[NMAX];
queue<int> Q;
stack<int> S;
int n,m;
void bf(int nod) {
Q.push(nod); Uz[nod] = true;
while(!Q.empty()) {
int x = Q.front(); Q.pop();
for ( int i = 0; i < A[x].size(); i++ ) {
if (!Uz[A[x][i]]) {
Uz[A[x][i]] = true;
Q.push(A[x][i]);
}
}
}
}
bool isEuler() {
bf(1);
for ( int i = 1; i <= n; i++ ) {
if (!Uz[i] || A[i].size() % 2) {
return false;
}
}
return true;
}
void removeEdge(int a, int b) {
for ( vector<int>::iterator it = A[a].begin(); it != A[a].end(); ++it) {
if (*it == b) {
A[a].erase(it);
break;
}
}
for ( vector<int>::iterator it = A[b].begin(); it != A[b].end(); ++it) {
if (*it == a) {
A[b].erase(it);
break;
}
}
}
void fillEuler(int nod) {
while (!A[nod].empty()) {
int x = A[nod][0];
removeEdge(nod, x);
S.push(nod);
nod = x;
}
}
vector<int> euler() {
vector<int> sol;
int last = 1;
do {
fillEuler(last);
last = S.top(); S.pop();
sol.push_back(last);
} while(!S.empty());
return sol;
}
int main() {
freopen(FILEIN, "r", stdin);
freopen(FILEOUT, "w", stdout);
scanf("%d %d", &n, &m);
for ( int i = 1, x, y; i <= m; i++ ){
scanf("%d %d", &x, &y);
A[x].push_back(y);
A[y].push_back(x);
}
if (!isEuler()) {
printf("-1");
return 0;
}
vector<int> sol = euler();
for ( int i = 0; i < sol.size(); i++ ) {
printf("%d ", sol[i]);
}
printf("\n");
return 0;
}