【一只蒟蒻的刷题历程】--- 问题 1433: [蓝桥杯][2013年第四届真题]危险系数(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

错误思路一

一开始的思路是找起点到终点的路径，把每条路径中各点都加到vector中，然后只要有加入过vector的，都计数，最后减去起点和终点，然后结果是这样的。。。。。。。

错误思路二

然后，我看了看样例，分析了起点到终点的两条路径
第一条：1 - 3 - 4 - 5 - 6
第二条： 1 - 3 - 5 - 6
于是，我又单纯的认为应该是找到点最少的那条路径才对，也就是1-3-5-6刚好四个点，减去起点1和终点6，刚好是2个和样例一样（这次稳了）
结果是这样的：

正确思路（不唯一，一定有好多想不到的骚操作）

如果只找点最少的路径就会存在一个问题，举个例子：
路径一： 1 - 3 - 5 - 6
路径二： 1 - 3 - 6
路径三： 1 - 5 - 6
可以看出，路径二和路径三都不是危险点，砍了3吧，5能走；砍了5吧，3能走；所以只有每条路径都有这个点（也就是说这个点在路径中出现的次数要等于路径数），才能算得上是危险点，因为这样才能保证，砍了这个点，每条路径都会断。
然后结果是：

代码附上：

#include <iostream>
#include <algorithm>
#include <string>
#include <queue>
#include <cstring>
#include <cmath>
#include <vector>
using namespace std;
const int maxn=1010;
int ans[maxn]={0};     //记录路径中某个点出现的次数
bool vis[maxn]={false}; //记录是否访问过
int n,m,a,b; 
int cntpath=0;    //累计路径条数
vector<int> path;   //存放路径
vector<int> g[maxn];  //存图
void dfs(int u,int end)   //dfs，u为起点，end为终点
{if(u==end)    //如果起点等于终点{cntpath++;  //路径++for(int i=0;i<path.size();i++) //累加每个点在路径中出现的次数ans[path[i]]++;return;}for(int i=0;i<g[u].size();i++)  //遍历u能到达的点{int v=g[u][i];if(vis[v]==false)  //没访问过就去访问{vis[v]=1;     //标记访问过path.push_back(v); //加入路径dfs(v,end);path.pop_back();  //回溯时，拿出路径vis[v]=0;   //标记没访问过}}
}int main() 
{cin>>n>>m;while(m--){cin>>a>>b;g[a].push_back(b);  //无向图存图g[b].push_back(a);} cin>>a>>b;vis[a]=1;   //标记起点访问过dfs(a,b);  //dfs（起点，终点）int cnt=0;for(int i=1;i<=n;i++)if(i!=a && i!=b && ans[i]==cntpath) /*起点不加，终点不加，该点出现cnt++;                          的次数等于路径条数，就代表每条路经都有这个点。因此删了这个点，每条路径都会断开，即为危险点*/if(!cnt)  //如果为初始值，代表到不了cout<<-1;elsecout<<cnt;return 0;
}