Pagini recente » Cod sursa (job #186413) | Cod sursa (job #796130) | Cod sursa (job #1533645) | Cod sursa (job #2282457) | Cod sursa (job #1336022)
#include <fstream>
#include <cstdlib>
#include <vector>
#include <queue>
#include <stack>
using namespace std;
ifstream cin("ciclueuler.in");
ofstream cout("ciclueuler.out");
#define nmax 100010
int n,m,x,y,gr[nmax],viz[nmax];
vector<int> g[nmax],v;
stack<int> st;
queue<int> q;
void bfs()
{
int nod;
vector<int>::iterator it;
q.push(1);
viz[1]=1;
while (!q.empty())
{
nod=q.front();
q.pop();
for (it=g[nod].begin();it!=g[nod].end();it++)
if (!viz[*it])
{
viz[*it]=1;
q.push(*it);
}
}
}
void sterge(int k,int v)
{
vector<int>::iterator it;
gr[k]--;
gr[v]--;
g[k].pop_back();
for (it=g[v].begin();it!=g[v].end();it++)
if (*it==k)
{
g[v].erase(it);
break;
}
}
void euler(int k)
{
int v;
while (1)
{
if (!g[k].size())
break;
v=*(g[k].rbegin());
sterge(k,v);
st.push(k);
k=v;
}
}
int main()
{
int i,j;
vector<int>::iterator it;
cin>>n>>m;
for (i=1;i<=m;i++)
{
cin>>x>>y;
g[x].push_back(y);
g[y].push_back(x);
gr[x]++;
gr[y]++;
}
bfs();
for (i=1;i<=n;i++)
{
if (gr[i]%2==1)
{
cout<<-1;
exit(0);
}
if (!viz[i])
{
cout<<-1;
exit(0);
}
}
x=1;
do
{
euler(x);
x=st.top();
st.pop();
v.push_back(x);
}while (!st.empty());
for (it=v.begin();it!=v.end();it++)
cout<<*it<<" ";
}