厦门市建设安全管理协会网站,北京好的做网站的公司,外贸网站制作价格表,做seo要明白网站内题目描述 问题描述 抗日战争时期#xff0c;冀中平原的地道战曾发挥重要作用。 地道的多个站点间有通道连接#xff0c;形成了庞大的网络。但也有隐患#xff0c;当敌人发现了某个站点后#xff0c;其它站点间可能因此会失去联系。 我们来定义一个危险系数DF(x,y)#xff…题目描述 问题描述 抗日战争时期冀中平原的地道战曾发挥重要作用。 地道的多个站点间有通道连接形成了庞大的网络。但也有隐患当敌人发现了某个站点后其它站点间可能因此会失去联系。 我们来定义一个危险系数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
解题思路 去除某个点c注意ca并且也cb去除之后若ab之间不存在通路则说明c是a,b之间必要的点计数器加1
思路参考链接 https://blog.csdn.net/weixin_41988545/article/details/86824844
代码如下
#include iostream
#include vector
#include cstring
using namespace std;
const int N 2010;
bool vis[N];
vectorintmp[N];
int s, e;
bool flag;
int ans;void dfs(int s) {if (s e) {flag 0;return ;}for (int i 0; i mp[s].size(); i) {if (!vis[mp[s][i]]) {vis[mp[s][i]] 1;dfs(mp[s][i]);vis[mp[s][i]] 0;}}
}int main() {int n, m;cin n m;for (int i 0; i m; i) {int a, b;cin a b;mp[a].push_back(b);mp[b].push_back(a);}cin s e;for (int i 1; i n; i) {memset(vis, 0, sizeof(vis));flag 1;vis[i] 1;for (int j 0; j mp[s].size(); j) {vis[mp[s][j]] 1;dfs(mp[s][j]);vis[mp[s][j]] 0;}if (flag)ans;}cout ans endl;return 0;
}
