Pagini recente » Rezultatele filtrării | Atasamentele paginii Profil agripinax36 | Cod sursa (job #414568) | Borderou de evaluare (job #404457) | Cod sursa (job #1237734)
#include<cstdio>
#include<vector>
using namespace std;
struct sp
{
int nod,ce;
bool be;
};
vector<int> ve[100005];
vector<int> ciclu[100005];
bool vi[100005];
int lu[100005],ncur,slf[100005],nra;
void dfs(int nod)
{
int i;
for(i=lu[nod]-1;i>=0;i--)
if(vi[ve[nod][i]]==0)
{
vi[ve[nod][i]]=1;
dfs(ve[nod][i]);
}
}
void sterg(int x,int y)
{
int i;
for(i=0;i<lu[x];i++)
if(ve[x][i]==y)
break;
for(i=i;i<lu[x];i++)
ve[x][i]=ve[x][i+1];
lu[x]--;
ve[x].pop_back();
}
void euler(int nod)
{
int i;
ciclu[ncur].push_back(nod);
if(nod==ncur)
{
ncur=-1;
return;
}
if(ncur==0)
ncur=nod;
i=ve[nod][lu[nod]-1];
sterg(i,nod);
ve[nod].pop_back();
lu[nod]--;
euler(i);
// printf("*");
if(ncur==-1)
return;
}
void afis(int nod)
{
while(slf[nod]!=0)
{
slf[nod]--;
printf("%d ",nod);
}
vi[nod]=1;
int x,i;
x=ciclu[nod].size();
for(i=0;i<x;i++)
{
nra--;
if(nra>0)
printf("%d ",ciclu[nod][i]);
if(vi[ciclu[nod][i]]==0)
afis(ciclu[nod][i]);
}
}
int main()
{
freopen("ciclueuler.in","r",stdin);
freopen("ciclueuler.out","w",stdout);
int n,m,i,j,x,y;
bool te=1;
sp tm;
scanf("%d%d",&n,&m);
for(i=1;i<=m;i++)
{
scanf("%d%d",&x,&y);
if(x==y)
slf[x]++;
else
{
lu[y]++;
ve[y].push_back(x);
ve[x].push_back(y);
lu[x]++;
}
}
vi[1]=1;
dfs(1);
te=1;
for(i=1;i<=n;i++)
{
if(vi[i]==0 || lu[i]%2==1)
te=0;
vi[i]=0;
}
if(te==0)
{
printf("-1\n");
}
else
{
for(i=1;i<=n;i++)
if(!ve[i].empty())
{
ncur=0;
euler(i);
// printf("%d ",ciclu[i][j]);
}
printf("1 ");
nra=m-1;
afis(1);
printf("\n");
}
return 0;
}