题目链接:http://acm.sgu.ru/problem.php?contest=0&problem=122
题意:构造哈密顿圈。
思路:对于任意两个点u和v的度之和大于等于n-1,则必存在哈密顿圈。构造的方法每本离散数学书上都有。
#include <iostream>
#include <stdio.h>
#include <string.h>
using namespace std;
bool a[1005][1005];
int visit[1005],ans[1005],n,m,num;
void reverse(int a,int b)
{
while(a<b)
{
swap(ans[a],ans[b]);
a++;
b--;
}
}
void deal()
{
int i,j,mid,flag;
num=0;
ans[num++]=1;
memset(visit,0,sizeof(visit));
visit[1]=1;
while(1)
{
while(1)
{
flag=0;
for(i=1;i<=n&&!flag;i++) if(!visit[i]&&a[ans[num-1]][i])
ans[num++]=i,flag=1,visit[i]=1;
if(!flag) break;
}
reverse(0,num-1);
while(1)
{
flag=0;
for(i=1;i<=n&&!flag;i++) if(!visit[i]&&a[ans[num-1]][i])
ans[num++]=i,flag=1,visit[i]=1;
if(!flag) break;
}
mid=0;
if(!a[ans[0]][ans[num-1]])
{
for(i=1;i<=num-2;i++) if(a[ans[i]][ans[num-1]]&&a[ans[0]][ans[i+1]])
{
reverse(i+1,num-1);
break;
}
}
if(num==n) break;
for(i=1;i<=n;i++) if(!visit[i])
{
for(j=1;j<=num-2;j++) if(a[i][ans[j]])
{
reverse(0,j-1);
reverse(j,num-1);
ans[num++]=i;
visit[i]=1;
break;
}
if(j<num-1) break;
}
}
}
void print()
{
int i,j;
for(i=0;i<num;i++) if(ans[i]==1) break;
for(j=0;j<num;j++)
{
printf("%d ",ans[i++]);
if(i==n) i=0;
}
puts("1");
}
int main()
{
while(scanf("%d",&n)!=-1)
{
memset(a,0,sizeof(a));
int i,k;
for(i=1;i<=n;i++)
{
while(1)
{
scanf("%d",&k);
a[i][k]=1;
k=getchar();
if(k=='\n'||k=='\r'||k==EOF) break;
}
}
deal();
print();
}
return 0;
}