万卷消永愁

用户名：uq_16083732442

访问量：6784

签　名：

等　　级
排　　名	3806
经　　验	1834
参赛次数	1
文章发表	28
年　　龄	0
在职情况	学生
学　　校
专　　业

　　自我简介：

TA的其他文章

纯代码无注释
浏览：118

纯代码无注释
浏览：140

一点代码注释
浏览：127

你可能喜欢

蓝桥杯2013年第四届真题-危险系数-题解（C++代码）

　　作者: 万卷消永愁　　　　发表时间：2020-10-18 16:10:07 浏览：218　|　评论：0　

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

此题就是在搜索算法的基础上，先屏蔽其间的一个点，再搜索，最后统计一共多少个关键点
```cpp
#include<cstring>
#include<iostream>
#include<set> 
using namespace std;
int to[2001],head[2001],last[2001],tot=0;//head数组是头顶点，to数组是head指向的下一个顶点，last用来保存head的上一次状态,tot一直增加，保证每个head都是不同的值 
int visit[2001];//标记顶点是否被访问过 
int u1,v1;//u1,v1是要判断的那两个顶点 
set<int> s;//set集合用来统计除了u1,v1之外的其它顶点 
int count=0;
void add(int u,int v)
{
	to[tot]=v;
	last[tot]=head[u];
	head[u]=tot;
	tot++;
}

void dfs(int u) //dfs也可以用二维数组 ，二维数组好理解，一维数组比较绕，难点就是如何将一个顶点对应的多个点都保存下来 
{

visit[u]=true;//将这个点标记为访问过了
	if(u==v1)//如果最后到达了v1那个点，count就会加1，就说明存在路径，此点就不是关键点 
	{
		count++;
		return;
	}
	for(int i=head[u];i!=-1;i=last[i])//如果这个顶点被访问过，就会判断last上一次还有没有连接其它顶点 
	{
		int j=to[i];
		if(!visit[j])
		{
			dfs(j);
		}
	} 
}
int main()
{
	memset(head,-1,sizeof head);
	int n,m;//n是顶点数,m是边数 
	int u,v;//u是顶点,v是顶点u指的下个顶点 
	cin>>n>>m;
	while(m--)
	{
		cin>>u>>v; 
		s.insert(u);
		s.insert(v);//set集合插入会自动去重 
		add(u,v);
		add(v,u);//无向图，所以要添加两次 
	}
	cin>>u1>>v1;
	s.erase(u1);//set集合可以直接删除一个数 
	s.erase(v1);//删除u1,v1之后就剩其它几个我们要判断是否是关键点的顶点 
	set<int>::iterator it=s.begin();
	for(it;it!=s.end();it++)//循环依次判断 
	{
		memset(visit,0,sizeof visit);//每次搜索之后就要将visit清零，方便下次重新搜索 
		visit[*it]=true;//将u1到v1之间的一个点置为被访问过，即断开连接，再进行下面搜索 
		dfs(u1);
	}
	cout<<s.size()-count;//count统计了不是关键点的顶点，s.size是除了u1,v1顶点的所有点，所以减去非关键点就是关键点了 
	return 0;
 } 
```

0.0分

0 人评分

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

万卷消永愁

TA的其他文章

你可能喜欢

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

C二级辅导-计负均正（C++代码）

C二级辅导-分段函数（C语言代码）

永远的丰碑（C语言代码）

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

蓝桥杯2013年第四届真题-危险系数-题解（C++代码）

评论区

精彩推荐

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

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

完数（C语言代码）

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

关于float，double变量的几点说明

矩形面积交（C++代码）

小九九（C语言描述,不看要求真坑爹）

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

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

1074(纳闷了,答案错误,求指教)

万卷消永愁

TA的其他文章

你可能喜欢

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

C二级辅导-计负均正 （C++代码）

C二级辅导-分段函数 （C语言代码）

永远的丰碑 （C语言代码）

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

蓝桥杯2013年第四届真题-危险系数-题解（C++代码）

评论区

精彩推荐

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

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

完数 （C语言代码）

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

关于float，double变量的几点说明

矩形面积交 （C++代码）

小九九 （C语言描述,不看要求真坑爹）

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

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

1074(纳闷了,答案错误,求指教)

C二级辅导-计负均正（C++代码）

C二级辅导-分段函数（C语言代码）

永远的丰碑（C语言代码）

　　评论区

完数（C语言代码）

矩形面积交（C++代码）

小九九（C语言描述,不看要求真坑爹）