无向图删除单边/单节点后不可达节点对计数问题求解

基础公式铺垫 #

所有节点的两两总对数为 total = n * (n - 1) / 2，不可达节点对数 = 总对数 - 所有连通块内部可达节点对数之和，其中单个连通块（大小为s）的内部可达对为 s * (s - 1) / 2。 #

问题1：删除单条边后的不可达节点对统计 #

核心逻辑：仅当删除的边是**桥（割边）**时，才会改变图的连通性，非桥边删除后不可达对数值和原图完全一致。
实现步骤：

• 第一步：预计算原图的不可达对数值origin_ans：遍历所有连通块，累加各连通块的内部可达对得到sum_origin，origin_ans = total - sum_origin。
• 第二步：用Tarjan算法遍历全图，找出所有桥，同时在DFS过程中统计每个子树的大小。对于每座桥，删除后会将所在的大小为S的连通块拆分为大小为s和S - s的两个连通块，新增的不可达对为s * (S - s)。
• 第三步：遍历所有原始边，非桥边的结果直接为origin_ans，桥的结果为origin_ans + s * (S - s)。

问题2：删除单个节点后的不可达节点对统计 #

核心逻辑：仅当删除的节点是割点时，才会将原连通块拆分为多个独立子连通块，非割点删除后只会减少节点总数，不会拆分原连通块。
实现步骤：

• 第一步：删除节点后剩余节点总数为n-1，对应总对数为new_total = (n-1) * (n-2) / 2。
• 第二步：用Tarjan算法遍历全图，找出所有割点，同时记录删除割点后拆分出的所有子树大小s1, s2 ... sk，剩余部分的大小为rest = S - 1 - sum(s1...sk)，其中S为割点所在原连通块的大小，减1是扣除被删除的割点本身。
• 第三步：计算删除割点后的可达对之和sum_new = sum(si*(si-1)/2) + rest*(rest-1)/2，对应不可达对为new_total - sum_new。
• 第四步：对于非割点，删除后原连通块大小从S变为S-1，可达对之和为sum_origin - (S - 1)，对应不可达对为new_total - (sum_origin - (S - 1))。

实现注意点 #

• 需处理图存在多个独立连通块的情况，不要默认图为连通图。
• 存储边时需记录原始输入的编号，避免Tarjan算法处理无向边的反向边时混淆对应关系。
• 子树大小可以在Tarjan的DFS过程中同步统计，无需额外遍历。

内容的提问来源于stack exchange，提问作者unglinh279