描述
ACMCLUB的花园有n种花,每种花都种在不同的地点,地点分别用1到n表示。不同的花之间可能有路,也可能没路,花园一共有m条路。现在小明想要从1开始走,把每种花都看一遍,且每种花仅看一遍,最后到达终点n,请写出程序判断小明能否实现目标。
输入
测试数据有多组。
每组输入的第一行为整数n(n<=20),接下来一行输入一个数字m,表示有m条路。再接下来输入m行,每行输入两个数字x和y,表示x与y有路相连,每条路都是双向可走的。数据保证不会有重复的路。
输出
对于每组测试数据输出一行,如果小明能够实现目标,则输出1,否则输出0。
样例输入1
5
4
1 2
1 3
1 4
2 5
6
6
1 3
3 2
1 2
3 4
4 5
5 6
样例输出1
0
1
import java.util.Scanner; //深搜回溯 public class Main { static int[][] d; static int n; static boolean flag; static boolean[] vis; //记录节点是否到达 public static void dfs(int s, int step) { if (step == n && s == n) { flag = true; return ; } if (s == n && step != n) return ; vis[s] = true; for (int i = 2; i <= n; i++) { if (!vis[i] && d[s][i] == 1) dfs(i, step + 1); } vis[s] = false; } public static void main(String[] args) { Scanner input = new Scanner(System.in); while (input.hasNext()) { n = input.nextInt(); int m = input.nextInt(); d = new int[n+1][n+1]; //输入双向边 for (int i = 1; i <= m; ++i) { int l = input.nextInt(); int r = input.nextInt(); d[l][r] = d[r][l] = 1; } flag = false; vis = new boolean[n+1]; dfs(1, 1); if (flag) System.out.println(1); else System.out.println(0); } } }
0.0分
13 人评分
【亲和数】 (C语言代码)浏览:501 |
C语言程序设计教程(第三版)课后习题8.6 (C语言代码)浏览:577 |
C语言程序设计教程(第三版)课后习题8.1 (C语言代码)浏览:517 |
C语言程序设计教程(第三版)课后习题1.5 (C语言代码)浏览:510 |
WU-C语言程序设计教程(第三版)课后习题11.11 (C++代码)(想学链表的可以看看)浏览:1342 |
1642题解浏览:706 |
罗列完美数 (C语言代码)浏览:490 |
格式化数据输出 (C语言代码)浏览:811 |
C语言程序设计教程(第三版)课后习题1.5 (C语言代码)浏览:539 |
C语言程序设计教程(第三版)课后习题9.6 (C语言代码)浏览:553 |