Pagini recente » Cod sursa (job #550824) | Cod sursa (job #3127919) | Cod sursa (job #663171) | Cod sursa (job #459367) | Cod sursa (job #1614245)
#include <bits/stdc++.h>
using namespace std;
const int nmax = 100009;
const int mmax = 500009;
ifstream fin("ciclueuler.in");
ofstream fout("ciclueuler.out");
vector < int > g[nmax];
int st[mmax] , mark[nmax] , p[mmax];
int n , m , top , i , x , y , sp;
int df(int x)
{
int r = 1;
for (int i = 0 ; i < g[x].size() ; ++i)
{
int y = g[x][i];
if (mark[y]) continue;
mark[y] = 1;
r += df(y);
}
return r;
}
bool check()
{
for (i = 1 ; i <= n ; ++i)
if (g[i].size() % 2)
return 0;
if (df(1) < n) return 0;
return 1;
}
void solve(int x)
{
while (g[x].size())
{
st[++top] = x;
int y = g[x].back();
g[x].pop_back();
for (vector < int > :: iterator it = g[y].begin() ; it != g[y].end() ; ++it)
if (*it == x)
{
g[y].erase(it);
break;
}
x = y;
}
}
void euler(int x)
{
while (true)
{
solve(x);
x = st[top--];
p[++sp] = x;
if (top == 0) break;
}
for (int i = 1 ; i <= sp ; ++i)
fout << p[i] << " ";
}
int main()
{
fin >> n >> m;
for (i = 1 ; i <= m ; ++i)
{
fin >> x >> y;
g[x].push_back(y);
g[y].push_back(x);
}
if (check())
euler(1);
else
fout << "-1" << '\n';
return 0;
}