Pagini recente » Cod sursa (job #860507) | Cod sursa (job #598110) | Cod sursa (job #2824505) | Cod sursa (job #888824) | Cod sursa (job #328272)
Cod sursa(job #328272)
#include <cstdio>
#include <queue>
#include <list>
#include <stack>
#include <vector>
#define pb push_back
#define nx 100005
using namespace std;
vector <int> G[nx];
list <int> L;
stack <int> St;
int gr[nx],N,M;
int conex()
{
queue <int> Q;
int viz[nx]={0},nr=1;viz[1]=1;
vector <int> :: iterator it;
for (Q.push(1);!Q.empty();Q.pop())
{
int r=Q.front();
for (it=G[r].begin();it!=G[r].end();++it)
if (!viz[*it])
{
Q.push(*it);
viz[*it]=1;
nr++;
}
}
if (nr<N) return 0;
return 1;
}
int imp()
{
for (int i=1;i<=N;++i)
if (gr[i]%2)
return 0;
return 1;
}
void euler (int p)
{
vector <int> :: iterator it,it2;
while (1) {
for (it=G[p].begin();it!=G[p].end() && *it==0 ;++it)
{ ; }
if (it==G[p].end()) break;
St.push(p);
for (it2=G[*it].begin();it2!=G[*it].end();++it2)
if (*it2==p)
{
*it2=0;
break;
}
if (*it==0) it++;
gr[p]--,gr[*it]--;
p=*it;
*it=0;
}
}
int main()
{
freopen("ciclueuler.in","r",stdin);
freopen("ciclueuler.out","w",stdout);
int i,x,y;
scanf("%d%d",&N,&M);
for (i=1;i<=M;++i)
{
scanf("%d%d",&x,&y);
gr[x]++,gr[y]++;
G[x].pb(y);
G[y].pb(x);
}
if (!conex() || !imp())
{
printf("-1\n");
return 0;
}
int p=1;
do
{
euler(p);
p=St.top();
St.pop();
L.pb(p);
} while (!St.empty());
list <int> :: iterator it;
for (it=L.begin();it!=L.end();++it)
printf("%d ",*it);
printf("\n");
fclose(stdin);
fclose(stdout);
return 0;
}