Pagini recente » Cod sursa (job #2245419) | Cod sursa (job #249087) | Cod sursa (job #2536884) | Cod sursa (job #1083484) | Cod sursa (job #917131)
Cod sursa(job #917131)
#include<stdio.h>
#include<queue>
#include<stack>
#include<vector>
using namespace std;
vector<int> sol,G[100005];
stack<int> st;
int viz[100005];
int n,deg[100005];
inline bool good()
{
for(int i=1;i<=n;i++)
if(deg[i]&1)
return false;
queue<int> q;
q.push(1);viz[1]=1;
while(!q.empty())
{
int nod=q.front();
for(vector<int>::iterator it=G[nod].begin();it!=G[nod].end();it++)
if(!viz[*it])
viz[*it]=1,q.push(*it);
q.pop();
}
for(int i=1;i<=n;i++)
if(viz[i]==0)
return false;
return true;
}
void euler(int nod)
{
int next;
while(!G[nod].empty())
{
next=G[nod].back();
st.push(nod);
G[nod].pop_back();
for(vector<int>::iterator it=G[next].begin();it!=G[next].end();it++)
if(*it==nod)
{
G[next].erase(it);
break;
}
nod=next;
}
}
int main()
{
freopen("ciclueuler.in","r",stdin);
freopen("ciclueuler.out","w",stdout);
int m,i,x,y;
scanf("%d%d",&n,&m);
for(i=1;i<=m;i++)
{
scanf("%d%d",&x,&y);
deg[x]++;G[x].push_back(y);
deg[y]++;G[y].push_back(x);
}
if(!good())
{
printf("-1\n");
return 0;
}
int nod=1;
do
{
euler(nod);
nod=st.top();st.pop();
sol.push_back(nod);
}while(!st.empty());
for(vector<int>::iterator it=sol.begin();it!=sol.end();it++)
printf("%d ",*it);
printf("\n");
return 0;
}