蓝桥杯2013年第四届真题-危险系数 （C++代码） 搜就完事！

解题思路:   根据题的意思找出一个点使两个城市不联通，那搜出的那个点就是关键点

                 这个题可以换一种思维去想怎样去找出那个点，在纸上画了下图我发现

                关键点每次都会经过，这必然就以为着，经过该关键点的次数就等于总联通的次数

                于是思路就出来了直接 ac

注意事项:  题的一开始容易让我带偏，直接想并查集，然后发现我用并查集我自己不能去表达出来

                可能是我菜了┭┮﹏┭┮

参考代码:

#include<bits/stdc++.h>
using namespace std;
int n,m;
vector<int>vc[2001];
int vis[2001];
int rcd[1001];
int ans;
int a,b;
void dfs(int x)
{
	if(x==b)
	{
	   ans++;
	   for(int i=1;i<=n;++i)
	   {
	   	if(vis[i]&&i!=b&&i!=a)
	   	rcd[i]++;
	   }
		return ;
	 } 
	for(int i=0;i<vc[x].size();++i)
	{
		if(!vis[vc[x][i]])
		{
			vis[vc[x][i]]=1;
			dfs(vc[x][i]);
			vis[vc[x][i]]=0;
		}
	}
}
int main()
{
	cin>>n>>m;
	for(int i=1;i<=m;i++)
	{
		int u,v;
		cin>>u>>v;
		vc[u].push_back(v);
		vc[v].push_back(u);
	}
	cin>>a>>b;
	vis[a]=1;
	dfs(a);
	int sum=0;
	for(int i=1;i<=n;i++)
	{
		if(rcd[i]==ans)
		sum++;
	}
	if(sum==0)
	cout<<-1;//这个测评机太水了，有些这个点都没考虑也能过
	else     //当没有关键点时就是-1
	cout<<sum;
	return 0;
}