问题分析

题目要求计算通信网络中每条线路（边）的风险度，定义为移除该边后网络中危险计算机（割点） 的数量

。

关键点：

危险计算机：移除后使网络不连通的计算机（即割点）。

线路风险度：移除该线路后，网络中危险计算机的数量。

算法思路

这个问题需要结合割点（Articulation Points） 和桥（Bridges） 的算法来解决。

寻找原图的割点：

    使用 Tarjan 算法 在 $O(N + M)$ 时间内找出所有割点。

分类讨论边的类型：

    非桥边：移除后图仍然连通，割点集合不变。风险度 = 原图割点数量。

    桥边：移除后图分裂成两个连通分量。需要重新计算每个分量中的割点数量并相加。

高效计算桥边的风险度：

    对每个桥边 $(u, v)$，从图中移除该边后，通过 DFS/BFS 找出两个连通分量。

    对每个分量单独运行 Tarjan 算法求割点数量。

    风险度 = 分量A的割点数 + 分量B的割点数。

复杂度分析

时间复杂度：$O(N + M)$ 用于初始的割点和桥检测。最坏情况下，对每个桥边处理两个连通分量，但总复杂度仍可接受。

空间复杂度：$O(N + M)$ 存储图结构和中间数据。