[蓝桥杯][2013年第四届真题]危险系数

题目链接：危险系数

解题思路：当去掉一个点z（z！=x，z!=y），要使得路径不通，那么只需要统计从点x到点y的所有总路径数，当经过一个点的次数等于总路径数，那么这个点就是符合要求的，即去掉这个点就能使得路径不同。

#include<bits/stdc++.h> #define x first #define y second #define mem(h) memset(h,-1,sizeof h) using namespace std; typedef long long LL; typedef unsigned long long ull; typedef pair<int,int>PII; typedef pair<double,double>PDD; namespace IO{ inline LL read(){ LL o=0,f=1;char c=getchar(); while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();} while(c>='0'&&c<='9'){o=o*10+c-'0';c=getchar();} return o*f; } }using namespace IO; //#############以上是自定义技巧（可忽略）########## const int N=1e3+7,M=2e3+7,INF=0x3f3f3f3f,mod=1e9+7,P=131; int h[N],e[M],ne[M],idx; int path[N]; int cnt[N]; bool st[N]; int total; int n,m; void add(int a,int b){ e[idx]=b,ne[idx]=h[a],h[a]=idx++; } void dfs(int u,int v,int k){//u表示当前点，v表示目标点，k表示当前已走过的路径有几个点 if(u==v){//到达目标点 total++;//总路径数+1 for(int i=0;i<k-1;i++){//k-1是因为最后一个点是目标点，目标点不算 cnt[path[i]]++;//这条路径上的每个点都+1 } return ; } for(int i=h[u];~i;i=ne[i]){//遍历这个点所相通的点 int j=e[i]; if(st[j])continue; st[j]=1; path[k]=j;//把下一个点放入路径 dfs(j,v,k+1); st[j]=0; } } int main(){ cin>>n>>m; mem(h);//初始化头指针数组（可参考链式向前星） for(int a,b,i=0;i<m;i++){ cin>>a>>b; add(a,b),add(b,a);//建边 } int u,v,ans=0; cin>>u>>v; dfs(u,v,0);//搜索总表示，已经经过每一个点次数 for(int i=1;i<=n;i++){ ans+=(cnt[i]==total); } cout<<ans<<endl; return 0; }