如果您为每个已删除的边计算无法相互访问的节点对

Question

问题：

给定一个包含 N 个节点和 M 条边的无向图。您需要解决 2 个问题：

• 问题 1：对于每条边 j (j : 1 -> M)，如果删除该边，请计算无法相互到达的节点数（这两个节点之间没有路径）。
• 问题 2：对于每个节点 i (i : 1 -> N)，如果删除该节点（同时删除了与其相连的所有边），计算无法到达每个节点的节点数其他.

示例：

N = 6, M = 7
1 2
2 3
3 1
3 4
4 5
5 6
6 4

（边描述为u - v）

结果：

• 对于每条边 j (j : 1 -> M): 0 0 0 9 0 0 0
• 对于每个节点 i (i : 1 -> N): 0 0 6 6 0 0

P/S:这个问题我想了很多天都找不到合适的答案

Answer 1

如果初始图是连通的，那么第一个问题就是bridges and the second one is searching of cut vertex / articulation points的搜索。

显示桥后得到连接组件的大小（有两个），需要的结果是大小的乘积（例如，大小为 2 的组件和大小为 3 的组件给出 6 对）

显示切割顶点后组件的数量可能会更大，结果是大小的成对乘积之和（对于大小为 1,2,3 的组件，结果是 1*2+1*3+2*3=11 对）

可以找到使用 DFS 解决这两个问题的 C++ 代码 here