Pagini recente » Cod sursa (job #3213681) | Cod sursa (job #2548296) | Cod sursa (job #238629) | Cod sursa (job #2751564) | Cod sursa (job #2462667)
#include <cstdio>
#include <vector>
#include <stack>
using namespace std;
vector <pair <int , int> > G[100005];
stack <int> st;
int ans[500005] , viz[500005] , n , m;
int valid()
{
int i;
for(i = 1 ; i <= n ; i ++)
if(G[i].size() % 2 == 1)
return 0;
return 1;
}
void euler()
{
int u , v , ok;
st.push(1);
while(!st.empty())
{
ok = 0;
u = st.top();
while(G[u].size() && viz[G[u].back().first])
G[u].pop_back();
if(G[u].size())
{
v = G[u].back().second;
viz[G[u].back().first] = 1;
G[u].pop_back();
st.push(v);
ok = 1;
}
if(!ok)
{
st.pop();
if(!st.empty())
ans[++ ans[0]] = st.top();
}
}
}
int main()
{
freopen("ciclueuler.in" , "r" , stdin);
freopen("ciclueuler.out" , "w" , stdout);
int i , u , v;
scanf("%d%d" , &n , &m);
for(i = 1 ; i <= m ; i ++)
{
scanf("%d%d" , &u , &v);
G[u].push_back(make_pair(i , v));
G[v].push_back(make_pair(i , u));
}
if(valid())
{
euler();
for(i = 1 ; i <= ans[0] ; i ++)
printf("%d " , ans[i]);
}
else
printf("-1\n");
return 0;
}