DFS · 素数环（HDU_1016）

DFS简析：

DFS（深度优先搜索） ，搜索方法是从起点开始，从某一方向一层一层往下找，直到最底层，

进行操作之后然后返回上一层换一个方向继续寻找，寻找方法有点类似根树遍历方法的前序遍历，一支一支找完之后，就完成了遍历

搜索。

实现这个算法很简单，其“本体”就是一个递归函数，如果某一方向的子支还不是最底层且满足题给条件，那么就继续调用它本身，

直到不满足递归条件（及达到最底层或不满足继续循环的条件），那么操作后进行返回，让其开始下一个方向的寻找。

不得不提到的是剪枝，DFS算法很容易超时，所以剪枝问题就是重中之重，不仅有题上所给的限定条件，一般还会有一系列的隐形条件，

但剪枝方法因题而异，此处也不方便细说。

下面看例题：（HDU_1016）

素数环问题，即给定一个数n，能不能将从1开始到n（n<=20）结束的n个数排列呈环状，并且使相邻的两个数之和为素数

输入有很多样例，每一个样例一个数n，且输入以0结尾，

对于每一个数n，首先输出"Case x:"，x为当前样例个数，若存在这样的环，则从1开始依次输出，若不存在则输出"no answer"

且每一个样例后都要输出一个空行。

怎么解决这个问题呢？

我首先用埃氏筛法得到一个长为四十的数表，若下标数为素数，则存入1，否则存入0，

其次用DFS搜索，如果能将这n个数全部按要求排列起来，那么就输出这个排列，

而其间有一个小小的剪枝，若输入一个奇数，且排成环，那么这个环中肯定会有两个奇数相邻，

而这两个奇数不可能都为1，所以他们的和一定为合数，所以直接输出"no answer"就好了

代码：

#include <iostream>
#include <cstring>

using namespace std;

int a[25];//存放排好的数
int b[40];//判断下标是否为素数的数表
int visited[25];//记录点是否被走过
int n;
int flag = 0;//记录是否存在素数环
void dfs( int m, int ans )
{
    a[ans] = m;
    visited[m] = 1;
    if( ans == n-1 )
    {
        if( b[m+1] )
        {
            for( int i(0); i < n; i++ )
            {
                if( i == 0 )
                {cout << a[i];continue;}
                cout << " " << a[i];
            }
            cout << endl;
            flag++;
        }
    }
    else
    {
        for( int i = 1; i <= n; i++ )
        {
            if( b[i+m] && !visited[i] )
                dfs( i, ans+1 );
        }
    }
    visited[m] = 0;
}
main()
{
    int t = 0;
    memset( b, 1 ,sizeof(b) );//埃氏筛法
    b[0] = 0; b[1] = 0;
    for( int i(0); i*i <= 40; i++ )
        if ( b[i] )
            for( int j = 2*i; j <= 40; j += i )
                b[j] = 0;
    while( cin >> n )//输入
    {
        if( !n )
            break;
        if( n%2 == 1 )//剪枝
        {
            cout << "Case " << ++t << ":
";
            cout << "no answer" << endl << endl;
        }
        memset( a, 0, sizeof(a) );
        memset( visited, 0, sizeof(visited) );
        cout << "Case " << ++t << ":
";
        dfs( 1, 0 );
        cout << endl;
        if( !flag )//若flag仍为0，说明名优任何的环形成，所以no answer
        {
            cout << "Case " << ++t << ":
";
            cout << "no answer" << endl << endl;
        }
    }
}