xr

用户名：dotcpp0639023

访问量：409

签　名：

等　　级
排　　名	2376
经　　验	2337
参赛次数	0
文章发表	5
年　　龄	23
在职情况	学生
学　　校
专　　业

　　自我简介：

TA的其他文章

危险系数dfs深搜回溯解题，详细注释
浏览：80

完全二叉树的权值最详细注释
浏览：82

后缀表达式公式
浏览：39

你可能喜欢

危险系数dfs深搜回溯解题，详细注释

　　作者: xr　　　　发表时间：2023-03-04 15:39:13 浏览：80　|　评论：0　

原题链接：蓝桥杯2013年第四届真题-危险系数

```java
import java.util.Scanner;

public class Main {
	static int n;	// 顶点
	static int m;	// 通道
	static int[][] map;
	static boolean[] visited;
	static int[] nodes;	// 每条可行路径上经过的点
	static int[] countArr;	// 可行路径上经过的点的次数
	static int count;	// 可行路径的数量
	static int res;	// 关键点
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		n = sc.nextInt();
		m = sc.nextInt();
		visited = new boolean[n+1];
		nodes = new int[n+1];
		countArr = new int[n+1];
		map = new int[n+1][n+1];
		// 构建无向图
		for(int i = 0; i < m; i++) {
			int u = sc.nextInt();
			int v = sc.nextInt();
			map[u][v] = map[v][u] = 1;
		}
		int start = sc.nextInt();
		int end = sc.nextInt();
		dfs(start, end, 0);
		if(count == 0) {	// 表示没有可行路径
			System.out.print(-1);
			return;
		}
		for(int i = 1; i<=n; i++) {
			if(countArr[i] == count && i != start && i != end) {
				res++;
			}
		}
		System.out.print(res);
	}
	/**
	 * @param start	起点
	 * @param end	终点
	 * @param index	搜索了第几次
	 */
	private
	private static void dfs(int start, int end, int index) {
		// TODO Auto-generated method stub
		if(start == end) {
			count++;
			for(int i = 0; i<index; i++) {
				// 记录可行路径经过的点的次数
				countArr[nodes[i]]++;
			}
			return;
		}
		for(int i = 1; i<=n; i++) {
			if(map[start][i] == 1 && !visited[i]) {
				visited[start] = true;
				// 将经过的点存进nodes
				nodes[index] = i;
				// 下一次深搜以i作为起点，因为无向图的搜索路径是 start->i->.....->end
				dfs(i,end,index+1);
				visited[start] = false;
			}
		}
	}
}
```

0.0分

1 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

xr

TA的其他文章

你可能喜欢

校门外的树（C++代码）

C语言训练-排序问题<1> （C语言代码）

【数组的距离】（C语言代码）

产生数（C++代码）（大数乘法也是可以避免的么hhhh）

三进制小数（C++代码）（第11位大于1.5才能进位）

危险系数dfs深搜回溯解题，详细注释

评论区

精彩推荐

C二级辅导-进制转换（C语言代码）

A+B for Input-Output Practice (IV) （C语言代码）

简单的a+b （C语言代码）

不容易系列2 （C语言代码）

小明A+B （C语言代码）

C语言程序设计教程（第三版）课后习题5.4 （C语言代码）

C语言程序设计教程（第三版）课后习题6.4 （C语言代码）

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

C语言训练-求s=a+aa+aaa+aaaa+aa...a的值（C语言代码）

xr

TA的其他文章

你可能喜欢

校门外的树 （C++代码）

C语言训练-排序问题<1> （C语言代码）

【数组的距离】 （C语言代码）

产生数 （C++代码）（大数乘法也是可以避免的么hhhh）

三进制小数 （C++代码）（第11位大于1.5才能进位）

危险系数dfs深搜回溯解题，详细注释

评论区

精彩推荐

C二级辅导-进制转换 （C语言代码）

A+B for Input-Output Practice (IV) （C语言代码）

简单的a+b （C语言代码）

不容易系列2 （C语言代码）

小明A+B （C语言代码）

C语言程序设计教程（第三版）课后习题5.4 （C语言代码）

C语言程序设计教程（第三版）课后习题6.4 （C语言代码）

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

C语言训练-求s=a+aa+aaa+aaaa+aa...a的值 （C语言代码）

校门外的树（C++代码）

【数组的距离】（C语言代码）

产生数（C++代码）（大数乘法也是可以避免的么hhhh）

三进制小数（C++代码）（第11位大于1.5才能进位）

　　评论区

C二级辅导-进制转换（C语言代码）

C语言训练-求s=a+aa+aaa+aaaa+aa...a的值（C语言代码）