李华

用户名：2645479600

访问量：18656

签　名：

等　　级
排　　名	478
经　　验	4691
参赛次数	2
文章发表	22
年　　龄	22
在职情况	学生
学　　校	华软、江理
专　　业	电信、计算机

　　自我简介：

欢迎探讨

TA的其他文章

蓝桥杯基础练习VIP-矩阵乘法-题解(C语言代码)---------错误14%的看过来
浏览：360

你可能喜欢

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

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

gets函数前有scanf读取时候，会读取缓存回车导致出错！！！

2004年秋浙江省计算机等级考试二级C 编程题(1) （C语言代码）

C语言训练-计算t=1+1/2+1/3+...+1/n （C语言代码）

[2013年第四届真题]危险系数-题解(C++代码)------STL，dfs

　　作者: 李华　　　　发表时间：2020-02-16 23:33:59 浏览：921　|　评论：5　

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

这是样例的连通图：
![](/image_editor_upload/20200216112158_52245.png)
解题思路:
1.计算能成功到达终点的路径有多少条
2.记录每次成功到达终点经过的点
3.哪个点的经过次数=成功路径数。那么它就是关键点
```cpp
#include <iostream>
#include <cstdio>
#include <vector>
using namespace std;
vector<int> vec[1005];	//用于记录每个站点连通的站点,不知道STL的话看作二维数组就好了 
int vis[1005];	//用于记录站点是否访问过 
int count=0;	//用于记录关键点的个数
int success_load=0;	//用于记录能成功到达的路径条数
int pass_by[1005];//用于记录全部成功路径路过某点的次数 
int u,v;	//起点,终点
int n,m; 
void dfs(int now)
{
	vis[now]=1;	//标记走过的点
	if(now==v)	//出口 
	{
		for(int i=1;i<=n;i++)
		{
			if(vis[i]==1)	pass_by[i]++;
		}
		success_load++;
		vis[now]=0;	//注意必须对对终点清零,如果不清零,下次再找终点,因为被标记过就走不进来了 
		return;
	} 
	for(int i=0;i<vec[now].size();i++) 
	{
		if(vis[vec[now][i]]==0)	//如果准备走的点没有被标记过,那么尝试走下去 
		{
			dfs(vec[now][i]);
		}
	}
	vis[now]=0;
}
int main(int argc, char** argv)
{
	cin >> n >> m;
	int a,b;
	for(int i=0;i<m;i++)
	{
		cin >> a >> b;
		vec[a].push_back(b);	//a与b连通，所以将与a站点连通的站点存入数组 
		vec[b].push_back(a);	//这是无向图，同理b也与a连通 
	}
	cin >> u >> v;	//读入起点,终点 
	dfs(u);//dfs的参数是当前的位置,从起点开始搜索，故传入起点的位置 
	for(int i=1;i<=n;i++)
	{
		if(pass_by[i]==success_load && i!=u && i!=v)	
		count++;
	}
	if(success_load==0)	cout << "-1" << endl; 
	else	cout << count << endl;
	return 0;
}
```

0.0分

21 人评分

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

　　评论区

LowStar

厉害厉害

2023-02-26 21:10:48

早起床

大佬厉害

2022-10-01 13:38:28

小哈哈

哪个点的经过次数=成功路径数。那么它就是关键点-------------------------------太棒了，我竟然没想到这个，这样省好多，我是最笨的方法，一个点一个点的去除，搞了两个搜索函数，虽然过了，都是太繁琐

2020-02-21 14:23:22

uq_41087421161

2020-02-20 19:07:26

uq_41087421161

2020-02-20 19:07:08

李华

TA的其他文章

你可能喜欢

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

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

gets函数前有scanf读取时候，会读取缓存回车导致出错！！！

2004年秋浙江省计算机等级考试二级C 编程题(1) （C语言代码）

C语言训练-计算t=1+1/2+1/3+...+1/n （C语言代码）

[2013年第四届真题]危险系数-题解(C++代码)------STL，dfs

评论区

精彩推荐

2003年秋浙江省计算机等级考试二级C 编程题(2) （C语言代码）

C语言训练-最大数问题（C语言代码）

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

P1001 （C语言代码）

2003年秋浙江省计算机等级考试二级C 编程题(2) （C语言代码）

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

WU-蓝桥杯算法提高VIP-勾股数（C++代码）

The 3n + 1 problem （C语言代码）

母牛的故事（C语言代码）

文科生的悲哀（C语言代码）

李华

TA的其他文章

你可能喜欢

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

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

gets函数前有scanf读取时候，会读取缓存回车导致出错！！！

2004年秋浙江省计算机等级考试二级C 编程题(1) （C语言代码）

C语言训练-计算t=1+1/2+1/3+...+1/n （C语言代码）

[2013年第四届真题]危险系数-题解(C++代码)------STL，dfs

评论区

精彩推荐

2003年秋浙江省计算机等级考试二级C 编程题(2) （C语言代码）

C语言训练-最大数问题 （C语言代码）

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

P1001 （C语言代码）

2003年秋浙江省计算机等级考试二级C 编程题(2) （C语言代码）

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

WU-蓝桥杯算法提高VIP-勾股数 （C++代码）

The 3n + 1 problem （C语言代码）

母牛的故事 （C语言代码）

文科生的悲哀 （C语言代码）

　　评论区

C语言训练-最大数问题（C语言代码）

WU-蓝桥杯算法提高VIP-勾股数（C++代码）

母牛的故事（C语言代码）

文科生的悲哀（C语言代码）