一道搜索题,想用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; }}