蓝桥杯2013年第四届真题-危险系数-题解（C++代码）图的邻接矩阵+图的遍历

解题思路:此题涉及到图的有关知识，先利用邻接矩阵的存储方式将各个定点存储起来 如顶点1和顶点3相连 则存储map[1][3]=3，

然后从初始顶点开始搜索，并记录下各顶点使用的次数和总路径数。如果顶点的使用次数和路径数相等，则该点即为关键点。

注意事项:初始顶点和目标顶点的使用次数是和路径数相同的，可以将算出的最终顶点数-2，也可以如程序中所写  i!=s&&i!=e.

在图的存储时可以采用动态数组存储的方法更节省空间。

参考代码:

#include<iostream>//图的存储结构 邻接矩阵存储 
using namespace std;
int n,m,s,e,k;
int map[1001][1001];
int vis[1001],sum[1001];
void dfs(int x)
{
	if(x==e)
	{
		for(int i=1;i<=n;i++)
		{
			if(vis[i]==1&&i!=s&&i!=e)
			{
				sum[i]+=1;
			}
		}
		k++;
		return ; 
	}
	for(int i=1;i<=n;i++)
	{
		if(map[x][i]!=0&&!vis[i])
		{
			vis[i]=1;
			dfs(map[x][i]);
			vis[i]=0;
		}
	}
}
int main()
{
	int count=0;
	cin>>n>>m;
	for(int i=1;i<=m;i++)
	{
		int u,v;
		cin>>u>>v;
		map[u][v]=v;
		map[v][u]=u;
	}
	cin>>s>>e;
	vis[s]=1;
	dfs(s);
	for(int i=1;i<=n;i++)
	{
		if(sum[i]==k&&k!=0)
		{
			count++;
		}
	}
	cout<<count;
	return 0;
}