Pagini recente » Cod sursa (job #1910778) | Cod sursa (job #62678) | Cod sursa (job #2677796) | Cod sursa (job #3139037) | Cod sursa (job #877739)
Cod sursa(job #877739)
#include<cstdio>
#include<vector>
#include<stack>
#define NMAX 100005
#define vec G[nod][i]
using namespace std;
int n,m;
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)
{
use[nod]=1;
for(size_t i=0;i<G[nod].size();i++)
if(!use[vec])
DFS(vec);
}
bool is_euler()
{
DFS(1);
for(int i=1;i<=n;i++)
if(!use[i])
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();
s.push(nod);
del(nod,x);
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;
}