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

222 阅读 0 评论 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 人评分

本文分类：题解列表
浏览次数：222 次浏览
发布日期：2023-03-04 15:39:13
本文链接：https://blog.dotcpp.com/a/94516

上一篇 > cou sabi jiashang dalaji鼠鼠的代码
下一篇 > 通俗易懂的C++方法

C语言网提供由在职研发工程师或ACM蓝桥杯竞赛优秀选手录制的视频教程，并配有习题和答疑，点击了解：

一点编程也不会写的：零基础C语言学练课程

解决困扰你多年的C语言疑难杂症特性的C语言进阶课程

从零到写出一个爬虫的Python编程课程

只会语法写不出代码？手把手带你写100个编程真题的编程百练课程

信息学奥赛或C++选手的必学C++课程

蓝桥杯ACM、信息学奥赛的必学课程：算法竞赛课入门课程

手把手讲解近五年真题的蓝桥杯辅导课程

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

评论列表共有 0 条评论

发表评论取消回复

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

一笔画问题（dfs）

C++ ： 类和两种访问权限的练习

C++ ： 类和两种访问权限的练习

幸运儿（约瑟夫环-模拟+ Vector）

评论列表 共有 0 条评论

发表评论 取消回复

C++ ：类和两种访问权限的练习

C++ ：类和两种访问权限的练习

评论列表共有 0 条评论

发表评论取消回复