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

重点就是：（点的访问次数）和（到达目的地路径条数）相等的点就是关键点。（也就是说每次到达终点都会访问的点就是关键点）
参考代码:

#include<bits/stdc++.h>
using namespace std;
int n, m,u,v,t=0,k=-1;//t记录到达终点路径条数，k表示关键点
vector<int> g[1000];
int vis[1000],vts[1000];//vis判断是否访问，vts记录所有路径到达终点时每个点的访问次数
void dfs(int x)
{
	if (x == v) //到达终点
	{
		for (int i =1; i <= n; i++)//记录频率
		{
			vts[i] += vis[i];
		}
		t++; //记录到达次数
		return;
	}
	vis[x] = 1;
	for (int i = 0; i < g[x].size(); i++)//访问邻接表
	{
		if (vis[g[x][i]] == 0) dfs(g[x][i]);
	}
	vis[x]=0;
}
int main()
{
	cin >> n >> m;
	for (int i = 1; i <= m; i++)
	{
		cin >> u >> v;
		g[u].push_back(v);//无向图双向赋值
		g[v].push_back(u);
	}
	cin >> u >> v;
	dfs(u);
	for (int i = 1; i <=n; i++)
	{
		if (vts[i] == t&&t!=0) k++;
	}
	cout << k;
}