当前位置 博文首页 > 爱新觉罗?炒饭的博客:蓝桥杯2013年第四届真题 危险系数
这道题主要抓住只需用dfs找到从起点到终点的路径数,统计经过的点,用times数组保存,当其中的点被访问的次数等于总路径数时,该点即为关键点。
#include<iostream>
using namespace std;
int map[1001][1001];//邻接矩阵
int path[1001];//存储路径
int vis[1001];//当前结点标志位
int times[1001];//存储结点经过的次数
int num=0,v;//num表示路径的数量,v表示终点
void DFS(int u,int n)
{
if(u==v)//到达终点时
{
num++;//路径数量加1
for(int i=1;i<=n;i++)
{
if(path[i])
{
times[i]++;//每个经过的结点次数加1
}
}
}
for(int i=1;i<=n;i++)
{
if(map[u][i]==1&&vis[i]==0)
{
vis[i]=1;
path[i]=1;
DFS(i,n);
vis[i]=0;//考虑后面还可能会经过i结点,所以要重新设置为0
path[i]=0;
}
}
}
int main()
{
int count=0,m,n,u;
for(int i=0;i<1001;i++)
{
vis[i]=path[i]=times[i]=0;
for(int j=0;j<1001;j++)
map[i][j]=0;
}
cin>>n>>m;
for(int i=0;i<m;i++)
{
cin>>u>>v;
map[u][v]=map[v][u]=1;
}
cin>>u>>v;
DFS(u,n);
if(num)
{
for(int i=1;i<=n;i++)
{
if(times[i]==num&&i!=u&&i!=v)//当路径数量和结点的次数相同,且结点不是终点和起点
count++;
}
cout<<count<<endl;
}
else
cout<<-1;
return 0;
}
cs