http://s14/mw690/ceb2fea6gdf7c65f2c8ad&690选座位" TITLE="图的dfs加回溯---小学组第二题 选座位" />

图的dfs递归回溯

#include

using namespace std;

#define maxn  10

#define  maxm   50

int n,m;

int a[maxn+1][maxn+1]={0};

int  visit[maxn]={0};//没有访问过

void read()

{

     int x,y;

     cout<<"请输入顶点个数和边的条数"<<endl;

     cin>>n>>m;    

     cout<<"请输入边的信息起点，终点"<<endl;

     for(int i=1;i<=m;i++)//读入M条的边

{

cin>>x>>y;

a[x][y]=1;//有边时，权植为1，没有边，权值为0

a[y][x]=1;//无向图

}

for(int i=1;i<=maxn;i++)

   visit[i]=0;//初始化所有的顶点都未访问 

}

 

 void  dfs(int k)//以顶点K为起点进行深搜

 {

visit[k]=1;//本顶点访问过了，作标记

 cout<<k<<"-->";

for(int i=1;i<=n;i++)

//搜索所有与本顶点相连的未访问过的顶点i       

if((a[k][i]==1)&&(visit[i]==0))

 dfs(i);

visit[k]=0;//回溯     

 }

int main()

{

    read();

for(int i=1;i<=n;i++)

 {

cout<<"现在以"<<i<<"为顶点dsf";

dfs(i);

cout<<endl;

 }

 system("pause");

    return 1;

}

 

 

 

 

2.换座位（shuffle）

 

在你的帮助下，聪聪很快解决了这个问题，信心又回来了。老师为了奖励聪聪这种知难

而进的精神，决定把今年的庆祝少先队建队 63 周年纪念活动中的游戏项目交给聪聪来策划。

聪聪可高兴了，他召集了班上的少先队员一起来讨论，最终确定了这样一个游戏：班上

共有 2N 个少先队员，开始时每个少先队员坐在自己的板凳上排成一队，由聪聪开始击鼓，

每次击鼓开始时，前 N 个同学坐到第 2、4、…、2N 个板凳上，后 N 个同学坐到第 1、3、…、

2N-1 个板凳上，击鼓结束时坐错或者还没有坐到对应板凳上的同学就要接受惩罚——表演

一个节目。聪聪不断的击鼓然后停顿后又击鼓，同学们都觉得这个游戏很好玩，但是当游戏

结束时，同学们傻眼了，由于每位同学的板凳都差不多，他们找不到自己的板凳了。这次聪

聪反应特别快，他说经过一定次数的换座位，每位同学一定能回到自己的板凳的。那么这个

次数最少是多少呢？你会计算吗？

【输入文件】

输入共一行，一个正整数 N。

【输出文件】

输出文件一个正整数，每位同学都回到自己板凳的最少换座位次数。

【输入输出样例】

 

shuffle.in

10

 

 

【数据范围】

1≤N≤10,000。

 

#include

using namespace std;

#define maxn  20000

int a[maxn],b[maxn];

int num;

int judge(int n)

{

    for(int i=1;i<=n;i++)

    if(b[i]==i)

      continue;

    else  return 0;//没做到正确的位置

  return 1;// 相等可以结束了

}

void read()

{

   int n;

    cin>>n;

for(int i=1;i<=2*n;i++)//存放以前的人

 a[i]=i;

for(int i=1;i<=2*n;i++)

 b[i]=i;

int num=0;

do

{

   num=num+1;

for(int i=1;i<=n;i++)

b[2*i]=a[i];//把前n个数移到b[2.4.6..2*n]

for(int i=n+1;i<=2*n;i++)

b[(i-n)*2-1]=a[i];//把后n个数移b[135..2*n-1]

  //b[1]--a[4] b[3]-a[5] b[5]--a[6]

if(judge(2*n)==1)

   break;

 else {

for(int i=1;i<=2*n;i++)

 a[i]=b[i];//把b又重新倒到a数组

      }

 }

while(1);//可以 结束了

cout<<num<<endl;

}

int main()

{

    read();

    system("pause");

    return 1;

 }