【洛谷 P8604】[蓝桥杯 2013 国 C] 危险系数题解（Tarjan算法+无向图+求割点+链式前向星+广度优先搜索）

本文主要是介绍【洛谷 P8604】[蓝桥杯 2013 国 C] 危险系数题解（Tarjan算法+无向图+求割点+链式前向星+广度优先搜索），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

[蓝桥杯 2013 国 C] 危险系数

题目背景

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

题目描述

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

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

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

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

输入格式

输入数据第一行包含 $2$ 个整数 $\le n \le 1000)$ ， $\le m \le 2000)$ ，分别代表站点数，通道数。

接下来 $m$ 行，每行两个整数 $\le u,v \le n,u\neq v)$ 代表一条通道。

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

输出格式

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

样例 #1

样例输入 #1

样例输出 #1

提示

时限 1 秒, 64M。蓝桥杯 2013 年第四届国赛

思路

先用Tarjan算法求割点，再用广度优先搜索求关键点。

Tarjan函数用于在图中找出所有的割点。割点是指，如果去掉这个点以及与它相连的边，会使得原本连通的图不再连通。Tarjan函数通过深度优先搜索（DFS）的方式来找出所有的割点。

对每个节点，将其深度优先搜索序号dfn和最早可回溯的节点序号low都初始化为0。如果它还未被访问过，则调用深度优先搜索。在搜索的过程中，维护一个全局的时间戳num，代表当前的搜索次序。每当访问到一个新的节点，就将其dfn和low值都设置为当前的时间戳，并将时间戳加1。

在深度优先搜索的过程中，如果遍历到一个子节点v，而这个子节点已经被访问过，那么就尝试用这个子节点的dfn值更新当前节点u的low值，即low[u] = min(low[u], dfn[v])。这一步表示，如果存在一个从u出发的回路可以回到v，那么u就可以通过这个回路回到v。

如果遍历到一个子节点v，而这个子节点还未被访问过，那么就对v进行深度优先搜索。在搜索结束后，尝试用v的low值更新u的low值，即low[u] = min(low[u], low[v])。这一步表示，如果v可以回到的最早的节点也可以被u到达，那么u就可以通过v回到这个节点。

在对一个节点u的所有子节点遍历结束后，检查是否存在一个子节点v，使得low[v] >= dfn[u]。如果存在，那么u就是一个割点。

bfs函数用来判断在移除特定节点后，起点和终点是否仍然连通。通过广度优先搜索，从起点开始，遍历所有可以到达的节点。

首先清空队列和访问标记位集，然后将起点加入队列。然后进行循环，每次从队列中取出一个节点，标记为已访问，然后遍历这个节点的所有邻接节点。

对于每一个邻接节点，如果它是终点，那么就返回true，表示起点和终点是连通的。如果这个邻接节点没有被访问过，并且不是被移除的节点，那么就将它加入到队列中。如果在遍历过程中没有找到终点，那么就返回false，表示起点和终点不连通。

注意

若起点就是终点，危险系数就是0，直接输出0即可。
需要判断起点和终点是否连通。若不连通，直接输出-1即可。
割点不一定是关键点，有可能存在这样的情况：路径上某个点是割点，但是移除该点后，仍能通过其他路径能到达终点。需要对每个割点进行判断，若移除该割点后无法到达终点的，才是路径上的关键点。举个例子：

样例输入

样例输出

对于这组样例数据，节点3、5、6和7是割点。节点6是一个割点，但不是路径（1到10）的关键点。因此，答案是3而不是4。

AC代码

#include <algorithm>
#include <bitset>
#include <cmath>
#include <cstring>
#include <iostream>
#include <queue>
#define AUTHOR "HEX9CF"
using namespace std;
using ll = long long;const int N = 1e6 + 7;
const int INF = 0x3f3f3f3f;
const ll MOD = 1e9 + 7;struct Node {int to;int next;
} edge[N];
int head[N];
int cnt = 0;int n, m;
int qu, qv;// tarjan
int num = 0;
int dfn[N], low[N];
bitset<N> cut;// bfs
queue<int> q1;
bitset<N> vis;void init() {cut.reset();memset(head, -1, sizeof(head));memset(dfn, 0, sizeof(dfn));memset(low, 0, sizeof(low));
}void add(int u, int v) {edge[cnt].to = v;edge[cnt].next = head[u];head[u] = cnt++;
}// 求割点
void tarjan(int u, int fa) {// 初始化dfn[u] = low[u] = ++num;int son = 0;for (int i = head[u]; ~i; i = edge[i].next) {int v = edge[i].to;if (v == fa) {continue;}if (!dfn[v]) {// 访问子节点tarjan(v, u);// 回溯时更新low[u] = min(low[u], low[v]);if (low[v] >= dfn[u]) {son++;if (u != fa || son > 1) {// u不是根节点或有两个以上子节点满足条件cut[u] = 1;}}} else {// 回溯时更新low[u] = min(low[u], dfn[v]);}}
}bool bfs(int rm) {// 初始化vis.reset();while (q1.size()) {q1.pop();}q1.push(qu);while (q1.size()) {int f = q1.front();// cout << f << endl;q1.pop();vis[f] = 1;for (int i = head[f]; ~i; i = edge[i].next) {int to = edge[i].to;if (to == qv) {// 能到达return 1;}if (vis[to] || to == rm) {continue;}// cout << to << " " << cut[to] << endl;q1.push(to);}}return 0;
}int main() {ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);init();cin >> n >> m;for (int i = 1; i <= m; i++) {int u, v;cin >> u >> v;add(u, v);add(v, u);}cin >> qu >> qv;if (qu == qv) {// 若起点就是终点，危险系数就是0。cout << 0 << "\n";return 0;}// 求割点tarjan(qu, qu);if (!bfs(0)) {// 起点和终点不连通，无法到达cout << -1 << "\n";return 0;}ll ans = 0;// 找出路径上的关键点for (int i = 1; i <= n; i++) {if (cut[i] && !bfs(i)) {// 移除该割点后无法到达终点的才是路径上的关键点ans++;}}cout << ans << "\n";return 0;
}