NOIP 提高 2010 第一轮 第 27 题：枚举全排列寻找哈密顿回路

题目

```
#include<iostream>
#include<cstring>
using namespace std;
const int SIZE=100;
int n,m,r[SIZE];
bool  map[SIZE][SIZE],found;
bool successful()
{
    int i;
    for(i=1;i<=n;i++)
        if(!map[r[i]][r[i%n+1]])
           return false;
    return true;
}
void swap(int *a,int *b)
{
    int t;
    t=*a;
    *a=*b;
    *b=t;
}
void perm(int left,int right)
{
    int i;
    if(found)
       return ;
    if(left>right)
    {
        if(successful())
        {
            for(i=1;i<=n;i++)
                cout<<r[i]<<' ';
            found=true;
        }
        return ;
    }
    for(i=left;i<=right;i++)
    {
        swap(r+left,r+i);
        perm(left+1,right);
        swap(r+left,r+i);
    }
}
int main()
{
    int x,y,i;
    cin>>n>>m;
    memset(map,false,sizeof(map));
    for(i=1;i<=m;i++)
    {
        cin>>x>>y;
        map[x][y]=true;
        map[y][x]=true;
    }
    for(i=1;i<=n;i++)
       r[i]=i;
    found=false;
    perm(1,n);
    if(!found)
        cout<<"No solution!"<<endl;
    return 0;
}
```
输入：
9 12  
1 2  
2 3  
3 4  
4 5  
5 6  
6 1  
1 7  
2 7   
3 8  
4 8  
5 9  
6 9  
输出：_________

请写出程序的输出结果。

答案

169548327

题解

考点定位

本题考「全排列搜索模拟」,对应大纲 4.3.3 搜索（难度【4】）。

程序：枚举 1..n 的全排列（字典序），检查相邻（含首尾）是否都为图中边，找第一条哈密顿回路。

解题过程

输入 9 12，边集：1-2,2-3,3-4,4-5,5-6,6-1（六边形）+ 1-7,2-7,3-8,4-8,5-9,6-9。字典序枚举排列，第一条哈密顿回路输出其排列：

从 1 开头依次尝试：1,2,…：环 1-2-3-4-5-6-1 不含 7,8,9；插入 7 于 1-2 间 → 1,7,2,3,4,5,6 回 1？6-1 ✓ 但缺 8,9。继续在 3-4 间插 8：1,2,3,8,4,5,6,7? 7 必须与 1、2 相邻……系统枚举字典序第一个可行排列：

1 6 9 5 4 8 3 2 7（对应官方答案 169548327）。

验证环：1-6 ✓,6-9 ✓,9-5 ✓,5-4 ✓,4-8 ✓,8-3 ✓,3-2 ✓,2-7 ✓,7-1 ✓。

易错提醒

① perm 的交换写法产生字典序枚举（swap 回溯保持原序）；② successful 检查的是环（含 r[n]→r[1] 回边），验证时别漏最后一条边。