Question

一道关于C++的深搜题，出了点问题，请高手解答

题目是：：：：
房间（room） 空间限制：256MB 时间限制：1s
Description
有n个房间以及m条双向通道。
你需要找到有多少条从1号房间出发到n号房间路径，使得每个房间都恰好经过了一次。
Input
第一行两个数n、m。
接下来m行，每行两个数x、y，描述一条连接房间x和房间y的通道。
保证每条通道连接两个不同的房间，并且每两个房间至多只有一条通道连接。
Output
一行一个数，表示满足要求的路径条数。

Range
1≤n≤10，0≤m≤n*(n-1)/2

Sample

room.in
5 7
1 2
1 3
3 2
3 4
1 5
5 4
4 2

room.out
2

两条路径分别是：1-2-3-4-5和1-3-2-4-5。

以下是本人的程序：：：：：
#include<iostream>
#include<cstdio>
using namespace std;
int n,m,a[1001][1001],ans=0,mark[1001];
void dfs(int k)
{
int i;
bool b;
mark[k]=1;
if (k==n)
{
b=true;
for (i=1;i<=n;i++) if (mark[i]==0) b=false;
if (b==true) ans++;
}
for (i=k+1;i<=n;i++)
{
if (a[k][i]==1) dfs(i);
mark[i]=0;
}
}
int main()
{
freopen("room.in","r",stdin);
freopen("room.out","w",stdout);
int i,x,y;
memset(a,0,sizeof(a));
memset(mark,0,sizeof(mark));
cin>>n>>m;
for (i=1;i<=m;i++)
{
cin>>x>>y;
a[x][y]=1;
a[y][x]=1;
}
dfs(1);
cout<<ans<<endl;
fclose(stdin);fclose(stdout);
return 0;
}
请高手找出问题并详细解释，感谢！

Answer 1

#include<iostream>
#include<cstdio>
using namespace std;
int n,m,a[1001][1001],ans=0,mark[1001];
void dfs(int k)
{
    int i;
    bool b;
    mark[k]=1;
    if (k==n) 
    {
        b=true;
        for (i=1;i<=n;i++) if (mark[i]==0) b=false;
        if (b==true) ans++;
    }
    for (i=1;i<=n;i++)
    {
        if (a[k][i]==1 && i!= k && mark[i]== 0)
		{
			dfs(i);
			mark[i] = 0;
		} 
    }
}
int main()
{
    freopen("in.txt","r",stdin);
    int i,x,y;
    memset(a,0,sizeof(a));
    memset(mark,0,sizeof(mark));
    cin>>n>>m;
    for (i=1;i<=m;i++)
    {
         cin>>x>>y;
         a[x][y]=1;
         a[y][x]=1;
    }
    dfs(1);
    cout<<ans<<endl;
    return 0;
}

dfs的第二个循环，i应该从头开始检查，不应该从k+1开始，从K+1开始的话，你从1走到3，就不会再去检查从3走2 的逻辑了。另外还要加上可走判断mark[i] == 0表示下个点还未走过。