Pagini recente » Cod sursa (job #1401199) | Cod sursa (job #2548083) | Cod sursa (job #3207654) | Cod sursa (job #2720593) | Cod sursa (job #878150)
Cod sursa(job #878150)
#include <cstdio>
#include <algorithm>
#include <list>
#include <vector>
using namespace std;
const int MAXN = 100001;
list<int> G[MAXN];
vector<int> sol;
int deg[MAXN];
bool vis[MAXN];
void dfs(int node)
{
vis[node] = true;
list<int>::iterator it;
for (it = G[node].begin(); it != G[node].end(); ++it) {
if (vis[*it])
continue;
dfs(*it);
}
}
void rem_edge(int v, int w)
{
G[v].pop_front();
list<int>::iterator it;
for (it = G[w].begin(); it != G[w].end(); ++it)
if (*it == v) {
G[w].erase(it);
break;
}
}
void euler(int v)
{
while (!G[v].empty()) {
int w = *G[v].begin();
rem_edge(v, w);
euler(w);
}
sol.push_back(v);
}
int main()
{
freopen("ciclueuler.in", "r", stdin);
freopen("ciclueuler.out", "w", stdout);
int n, m;
scanf("%d %d", &n, &m);
for (int i = 0; i < m; ++i) {
int x, y;
scanf("%d %d", &x, &y);
G[x].push_back(y);
deg[x]++;
G[y].push_back(x);
deg[y]++;
}
dfs(1);
for (int i = 1; i <= n; ++i)
if (!vis[i]) {
printf("-1\n");
return 0;
}
for (int i = 1; i <= n; ++i)
if (deg[i] % 2 != 0) {
printf("-1\n");
return 0;
}
euler(1);
reverse(sol.begin(), sol.end());
for (int i = 0; i < sol.size() - 1; ++i)
printf("%d ", sol[i]);
printf("\n");
return 0;
}