读书人

一道搜索题想用DFS写但不懂如何写

发布时间: 2012-08-09 15:59:21 作者: rapoo

一道搜索题,想用DFS写,但不懂怎么写 求高人指教!!
Description:
佳佳正在规划着一次骑自行车的长途旅行,她想要走遍n个城市之间所有的路,而且每条路只能走一次,并且最终要回到出发点。
问题简化后也就是,有n座城市,之间有m条路,每条路连接其中的两座城市,佳佳从其中一座城市出发,经过所有的m条路一次且仅一次,最后回到出发的那座城市。佳佳想知道这个旅行计划能否实现。
Input:
有多组测试数据,每组测试数据的第一行输入两个整数n和m(1<=n<=20),下面紧接着输入m行数据,每行两个整数a和b(1<=a,b<=n),表示城市a与城市b之间有一条路径。
Output:
每组测试数据输出一行,"Yes"表示佳佳的计划能实现,"No"表示不能实现。
Example Input:

3 3
1 2
2 3
3 1

3 2
3 2
2 1

Example Output:

Yes
No

[解决办法]

C/C++ code
//楼主递归退出条件写错位置了int DFS (int x){    int i;    count++;    /*if (x == 0 && count == n)    {        return 1;    }*/    if (x != 0)    {        visit[x] = 1;    }    for (i = 0;i < n; i++)    {        if (a[x][i] && visit[i] == 0)        {            DFS (i);        }    }    if (x == 0 && count == n)    {        return 1;    }    else    {        return 0;    }} 

读书人网 >C语言

热点推荐