NOIP 提高组初赛 · 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 输出：_________

这题考全排列回溯找哈密顿回路。拿到题先看successful函数在查什么——它只验证相邻两点是否有边且没重复访问，所以核心是：先理解successful的判定条件，再顺着perm的全排列回溯流程，想象从第一个数开始一个个换位置，直到凑出一条满足条件的回路。

很多学生一看到全排列就慌，直接背模板，忽略了successful函数里两个关键细节：一是map数组是无向图的邻接矩阵，题目给的边是双向的，代码里map[x][y]=true和map[y][x]=true都设了，所以检查时不用管方向；二是successful只遍历1到n，看map[r[i]][r[i%n+1]]是否为true，这意味着它检查的是排列中相邻元素（包括首尾）是否都有边，但并没有显式检查“每个点只出现一次”——因为perm本身生成的就是全排列，每个点天然只出现一次，所以successful默认认为点不重复。如果题目改成允许重复点，successful就要加判断。另外，学生常把perm里的递归逻辑搞反，以为swap是原地修改原数组，其实perm每次把当前层r[left]和r[i]交换，递归进去，回来再换回去，这样回溯完r数组才恢复原状，不会污染后面的分支。还有，输入数据里有些点没连边（比如7只连了1和2），如果排列里把7放在中间，successful就会直接返回false，导致回溯剪枝，这也是为什么输出里7在最后的原因。

考点与概念 这题考查的是图论中的哈密顿回路问题，用回溯法（也叫深度优先搜索DFS的一种特例）来暴力枚举所有可能的顶点排列，然后对每个排列用successful函数验证是否构成合法回路。哈密顿回路定义：经过图中每个顶点恰好一次，且相邻顶点之间有边相连的闭合路径。本题n=9，m=12，边构成一个六边形（1-2-3-4-5-6-1）外加几条“桥”边（1-7,2-7,3-8,4-8,5-9,6-9），整体像个环加几条尾巴。

successful函数的作用 successful函数只负责“验证”：它循环i从1到n，检查map[r[i]][r[i%n+1]]是否为true。这里r[i%n+1]巧妙地处理了首尾相连——因为i%n+1当i=n时变成1，所以最后一个点和第一个点也被检查了。由于map是双向赋值的，只要两点间有边，map[x][y]和map[y][x]都true，所以successful不会误判方向。

perm函数的回溯逻辑 perm是典型的回溯模板：参数left和right表示当前要排列的区间[r[left]...r[right]]。递归终止条件是left>right，此时整个数组已是一个完整排列，就调用successful检查。如果successful返回true，输出当前排列并设置found=true，直接返回（因为题目只要第一个解）。 在递归过程中，for循环从i=left到right，每次把r[left]和r[i]交换，然后递归perm(left+1,right)，递归回来后再交换回去（回溯）。这样就能枚举出所有排列，但不会重复。

输入数据与图的直观 输入n=9,m=12，边列表： 1-2,2-3,3-4,4-5,5-6,6-1 → 形成一个六边形环，顶点1,2,3,4,5,6连成圈。 1-7,2-7 → 7只连了1和2，像个“耳朵”挂在1和2之间。 3-8,4-8 → 8连了3和4，挂在3和4之间。 5-9,6-9 → 9连了5和6，挂在5和6之间。 所以整个图是三个“尾巴”挂在六边形上，每个尾巴只有一个点（7,8,9）。

回溯过程推演（关键几步） perm从r=[1,2,3,4,5,6,7,8,9]开始，left=1。

• 先试r[1]=1，递归perm(2,9)。

- 在perm(2,9)里，r[2]依次试2,3,4,5,6,7,8,9。 - 试r[2]=2时，继续往下，最终会走到r[6]=6，此时前6个是1,2,3,4,5,6，刚好是六边形顺序，但successful检查时，map[6][7]是false（7只连1和2），所以失败，回溯。 - 试r[2]=6时，前两个变成1,6，接下来perm(3,9)里r[3]会试9（因为9只连5和6，如果放在3位置，map[9][5]还没检查，但后面会走到5，此时前三个是1,6,9，map[9][5]为true，继续... - 继续往下，r[4]试5，r[5]试4，r[6]试8（8连3和4，此时前面有3,4,8，map[8][3]为true，继续），r[7]试3，r[8]试2，r[9]试7。 - 此时排列：1,6,9,5,4,8,3,2,7。 - successful检查： 1-6: true（六边形边） 6-9: true（5-9,6-9给出的边） 9-5: true（5-9） 5-4: true（4-5） 4-8: true（4-8） 8-3: true（3-8） 3-2: true（2-3） 2-7: true（2-7） 7-1: true（1-7） - 全部为true，successful返回true，found=true，输出该排列。 这就是题目给出的正确答案。

易错点深挖 1. 误以为successful还要检查“每个点只出现一次”：其实perm生成的是全排列，天然满足，successful只管边。 2. 把swap理解成原地修改原数组：perm里swap后递归，回来又swap回去，回溯完r数组恢复原状，不会污染后续分支。 3. 忽略无向图的双向赋值：题目给的边是双向的，代码里map[x][y]=true和map[y][x]=true都设了，所以检查时不用管方向；如果只设map[x][y]，successful就会漏判反向边，导致错误。 4. 以为7,8,9可以放在中间：7只连1和2，8只连3和4，9只连5和6，所以它们只能出现在排列的末尾（与对应六边形点相邻），否则map[r[i]][r[i%n+1]]必为false，successful直接返回false，回溯剪枝。 5. 把perm的递归顺序搞反：perm是从left到right枚举，不是从right到left，所以第一个解往往是“尽量靠前”的排列，本题里7被推到最后，正是因为它只能在1或2旁边，而1已经在开头，2在倒数第二，所以7只能放最后。

考频与趋势 回溯法在题库共考过9题，覆盖6个考试级别（2007-2025），逐年分布：2007年1题、2009年1题、2010年1题、2012年1题、2020年1题、2025年4题。分赛事：NOIP提高组初赛3题、GESP五级2题、CSP提高级1题、GESP八级1题、CSP入门级1题、NOIP普及组初赛1题。 DFS（深度优先搜索）考频更高，共61题，覆盖7个级别，逐年：2009年1题、2010年1题、2013年3题、2020年2题、2021年1题、2022年1题、2023年6题、2024年13题、2025年9题、2026年22题、null年2题。分赛事：GESP七级20题、GESP六级16题、GESP八级11题、CSP提高级5题、CSP入门级4题、NOIP提高组初赛3题、NOIP普及组初赛2题。

预测 从数据看，2024年DFS考13题、2025年考9题、2026年考22题，明显呈上升趋势，说明回溯/DFS类题目在近年越来越受命题人青睐，尤其是NOIP提高组初赛和GESP高级别（七级、六级、八级）。回溯法本身考得少（9题），但往往和DFS捆绑出现，比如用DFS做迷宫、排列、组合优化等。未来几年，大概率会继续考“全排列+回溯找特定回路/路径”这类综合题，难度可能从单纯验证边，升级到带权最短哈密顿回路、或者需要剪枝优化（比如记录已访问集合用位运算）。如果2026年DFS考22题，其中可能有5-8题直接或间接涉及回溯思想，学生若只背模板而不懂successful背后的判定逻辑，很容易在复杂图上栽跟头。

综上，这题的核心就是读懂successful的验证逻辑，顺着perm的回溯流程，想象从第一个数开始一个个换位置，直到凑出一条满足条件的回路。记住：全排列天然不重复，successful只管边；无向图要双向赋值；尾巴点只能放末尾；swap是回溯的关键，别把数组搞脏了。