Pagini recente » Cod sursa (job #1882678) | Cod sursa (job #630363) | Cod sursa (job #464362) | Cod sursa (job #3222518) | Cod sursa (job #1027471)
#include<fstream>
using namespace std;
ifstream fin("ciclueuler.in");
ofstream fout("ciclueuler.out");
int m,n,a[100][100],sol[100],d[100];
bool s[100];
void bfs(bool *s, int i)
{
s[i]=1;
int j;
for(j=1;j<=n;j++)
if(a[i][j] and !s[j])
bfs(s,j);
}
bool isconex(int j)
{
int i;
for(i=1;i<=n;i++)
s[i]=0;
bfs(s,j);
for(i=1;i<=n;i++)
if(s[i]==0 and d[i])
return false;
return true;
}
void euler (int i)
{
int j;
for(j=1;j<=n;j++)
if(a[i][j])
{
a[i][j]=a[j][i]=0;
d[i]--;d[j]--;
if(!isconex(j))
{
a[i][j]=a[j][i]=1;
d[i]++;
d[j]++;
}
else
{
sol[++sol[0]]=j;
euler(j);
return;
}
}
}
int main()
{
fin>>n>>m;
int i,x,y;
for(i=1;i<=m;i++)
fin>>x>>y,a[x][y]=a[y][x]=1,d[x]++,d[y]++;
sol[0]=sol[1]=1;
euler(1);
for(i=1;i<=n;i++)
if(d[i])
{fout<<"-1";return 0;}
for(i=1;i<=sol[0];i++)
fout<<sol[i]<<" ";
return 0;
}