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

解题思路:我是菜鸡，我的想法是，关键点的含义就是从a到b的必经点。既然如此，设置一个数组x，设i为必经点，a到b有几条路径，x[i]就等于几。这样，每次深度优先搜索可以把途径的点先压入栈中，如果能达到b，则栈中所有点i让x[i]++，最后x数组中的最大值有多少个，也就有多少个必经点。

注意事项:提前把a和b压入栈中，设置visited数组防止图中的环导致的死循环。

参考代码:

#include<iostream>
#include<stack>
using namespace std;
int M,N; 
int edge[1000][1000]={0};
int x[1000]={0};
stack<int> q;
stack<int> p;//用于将q内的元素取出并让x[i]++
void f(int a,int b,bool* v)
{
	for(int i=1;i<=M;i++)
	{
		if(edge[a][i]==1&&!v[i])
		{
			if(i==b)//说明能够到达b点，则将这条路径经过的点取出，让x[i]++
			{
				p=q;
				while(!p.empty())
				{
					x[p.top()]++;
					p.pop();
				}
			}
			else
			{
				q.push(i);
				v[i]=true;
				f(i,b,v);
				q.pop();// f之后相当于a,i这个路径搜索完了，让i出栈 
				v[i]=false;// a,i搜索完了以后，别人也要用i，所以v[i]=false 
			}
		}
	}
}
int main()
{
	cin>>M>>N;
	int a,b;
	for(int i=0;i<N;i++)
	{
		cin>>a>>b;
		edge[a][b]=1;
		edge[b][a]=1;
	}
	cin>>a>>b;
	bool* visited=new bool[M];//是否访问过
	for(int i=1;i<=M;i++)
	{
		visited[i]=false;
	}
	visited[a]=true;
	q.push(a);
	q.push(b);
	f(a,b,visited);
	int max=0;
	for(int i=1;i<=M;i++)
	{
		if(max<x[i])
		max=x[i];
	}
	if(max==0)
		cout<<-1;//如果没有路径 
	else
	{
		int count=-2;//输出的必经点不包括a和b 
		for(int i=1;i<=M;i++)
		if(x[i]==max) count++;
		cout<<count;
	}
	return 0; 
}//我是菜鸡，所以写的有点乱，不喜勿喷呜呜呜