Pagini recente » Cod sursa (job #2525140) | Cod sursa (job #2636817) | Cod sursa (job #262276) | Cod sursa (job #1331027) | Cod sursa (job #877748)
Cod sursa(job #877748)
#include<cstdio>
#include<vector>
#include<stack>
#define NMAX 100005
using namespace std;
int n,m,nr;
vector<int> G[NMAX];
bool use[NMAX];
stack<int> s,sol;
void read()
{
freopen("ciclueuler.in","r",stdin);
scanf("%d %d",&n,&m);
int x,y;
for(int i=0;i<m;i++)
{
scanf("%d %d",&x,&y);
G[x].push_back(y);
G[y].push_back(x);
}
}
void DFS(int nod)
{
nr++;
use[nod]=1;
for(size_t i=0;i<G[nod].size();i++)
if(!use[G[nod][i]])
DFS(G[nod][i]);
}
bool is_euler()
{
DFS(1);
if(nr!=n)
return 0;
for(int i=1;i<=n;i++)
if(G[i].size()%2)
return 0;
return 1;
}
void del(int x,int y)
{
vector<int>::iterator it;
for(it=G[x].begin();it!=G[x].end();it++)
if(*it==y)
{
G[x].erase(it);
return;
}
}
void euler(int nod)
{
int x;
while(true)
{
if(G[nod].empty())
return;
x=G[nod].front();
G[nod].erase(G[nod].begin());
s.push(nod);
del(x,nod);
nod=x;
}
}
void solve()
{
freopen("ciclueuler.out","w",stdout);
if(!is_euler())
{
printf("-1");
return;
}
int x=1;
do
{
euler(x);
x=s.top();
s.pop();
sol.push(x);
}while(!s.empty());
while(!sol.empty())
{
printf("%d ",sol.top());
sol.pop();
}
}
int main()
{
read();
solve();
return 0;
}