题目1433:蓝桥杯2013年第四届真题-危险系数

#include<iostream>
#include<vector>
using namespace std;
int map[1010][1010];//创建邻接表
int vis[1010];//标记此节点是否访问过
int num[1010];//记录此节点出现过几次
int n,m;//站点数和通道数
int sum=0;//路径数量
vector<int>v;//存储顶点序列
void dfs(int cur,int target){//现在位置，目标位置
if(cur==target){
sum++;//可达路径数加1
for(int i=0;i<v.size();i++){
num[v[i]]++;//把遇到的所有节点都记录下来
}
return;
}
for(int i=1;i<=n;i++){
if(vis[i]==0&&map[cur][i]){
v.push_back(i);
vis[i]=1;
dfs(i,target);
vis[i]=0;
v.pop_back();
}
}
}
int main(){
cin>>n>>m;
int u,v,ans=0;
for(int i=0;i<m;i++){
cin>>u>>v;
map[u][v]=map[v][u]=1;
}
int start,target;
cin>>start>>target;
vis[start]=1;//将开始的点记为1，将不会被计数
dfs(start,target);
for(int i=1;i<=n;i++){
if(num[i]==sum){
ans++;
}
}
if(ans>1){
cout<<ans-1<<endl;
}else{
cout<<-1<<endl;
}
return 0;
}