历届试题 危险系数-（dfs+记录路径）

 历届试题 危险系数  

问题描述

抗日战争时期，冀中平原的地道战曾发挥重要作用。

地道的多个站点间有通道连接，形成了庞大的网络。但也有隐患，当敌人发现了某个站点后，其它站点间可能因此会失去联系。

我们来定义一个危险系数DF(x,y)：

对于两个站点x和y (x != y), 如果能找到一个站点z，当z被敌人破坏后，x和y不连通，那么我们称z为关于x,y的关键点。相应的，对于任意一对站点x和y，危险系数DF(x,y)就表示为这两点之间的关键点个数。

本题的任务是：已知网络结构，求两站点之间的危险系数。

输入格式

输入数据第一行包含2个整数n(2 <= n <= 1000), m(0 <= m <= 2000),分别代表站点数，通道数；

接下来m行，每行两个整数 u,v (1 <= u, v <= n; u != v)代表一条通道；

最后1行，两个数u,v，代表询问两点之间的危险系数DF(u, v)。

输出格式

一个整数，如果询问的两点不连通则输出-1.

样例输入

7 6
1 3
2 3
3 4
3 5
4 5
5 6
1 6

样例输出

2

思路：一直用dfs记录点访问过的次数，一路wa后才知道，记录的应该是能够从起点搜到终点的路径，这条路径上的点才是有效访问的点。通过关键点的次数 = 搜到路径的次数，表示，想要通向终点，必然要路过这个点。

 #include<stdio.h>

 #include<iostream>

 #include<algorithm>

 #include<cstring>

 #include<math.h>

 #include<string>

 #include<map>

 #include<queue>

 #include<stack>

 #include<set>

 #define ll long long

 #define inf 0x3f3f3f3f

 using namespace std;

 int n,m;

 vector<int>a[];

 bool vis[];

 int num[];

 int way[];

 int s,e;

 bool flag;

 int cnt=;

 void dfs(int x,int step)///当前点，步数

 {

     way[step]=x;///这一步数的点是x，如果没有搜到，重新搜索时候会覆盖路径

     if(x==e)

     {

         flag=true;

         cnt++;

         for(int i=;i<=step;i++)///深搜到终点作为一条完整的路径，这条路径共s步，把经过点的次数+1

             num[ way[i] ]++;

         return;

     }

     for(int i=;i<a[x].size();i++)

     {

         int to=a[x][i];

         if(!vis[to])///对没有访问过的点进行搜索

         {

             vis[to]=true;

             dfs(to,step+);

             vis[to]=false;

         }

     }

 }

 int main()

 {

     memset(vis,false,sizeof(vis));

     scanf("%d%d",&n,&m);

     while(m--)

     {

         int x,y;

         scanf("%d%d",&x,&y);

         a[x].push_back(y);

         a[y].push_back(x);

     }

     scanf("%d%d",&s,&e);

     vis[s]=true;

     dfs(s,);

     int ans=;

     if(flag)

     {

         for(int i=;i<=n;i++)

         {

             if(i==s || i==e)

                 continue;

             if(num[i]==cnt)///计数

                 ans++;

         }

     }

     else

         ans=-;

     printf("%d\n",ans);

     return ;

 }