无向图删除边或节点后两节点路径存在性查询方案问询

你之前的思路方向是完全正确的，这个问题可以通过预处理双连通分量+构造圆方树的方案实现单次查询O(logN)的效率，完全符合数据规模要求，具体实现思路如下：

首先用Tarjan算法对无向图做一次遍历，一次性得到三类信息：

• 所有的桥（删除后会增加连通块数量的边）
• 所有的割点（删除后会增加连通块数量的点）
• 每个节点所属的边双连通分量编号，存在belong[]数组中

边双连通分量的查询优化 #

你提到的「判断两个节点是否属于同一个双连通分量」其实不需要O(logN)的复杂度，边双连通分量的编号是每个节点唯一对应一个的，直接判断belong[A] == belong[B]就可以，时间复杂度是O(1)。

类型1：删除边U-V后A、B是否连通 #

按顺序判断即可：

1. 先判断原无向图中A和B是否连通，如果原本就不连通，删除边后肯定也不连通
2. 判断U-V是否是桥：
   • 如果不是桥：删除这条边不会影响图的连通性，A和B原本连通就仍然连通
   • 如果是桥：删除这条桥会把边双缩点树分成两个子树，只要判断A和B对应的边双节点是否还在同一个子树即可。可以通过预处理边双缩点树的DFS入序in[]和出序out[]，O(1)完成判断。

类型2：删除节点X后A、B是否连通 #

需要额外构造圆方树处理割点的相关判断：

• 构造规则：原图的普通节点作为圆点，每个点双连通分量对应一个方点，每个点双内的所有节点都和对应的方点连边，最终得到的树结构就是圆方树
• 预处理圆方树的LCA（最近公共祖先）倍增表，单次LCA查询复杂度O(logN)

查询判断逻辑：

1. 先判断原无向图中A和B是否连通，如果原本就不连通，删除X后肯定也不连通
2. 如果AX或者BX，直接返回不连通
3. 判断X是否是割点：
   • 如果不是割点：删除X不会改变其他节点的连通性，A和B原本连通就仍然连通
   • 如果是割点：等价于判断圆方树上A到B的路径是否经过X。如果路径经过X，删除后A、B就不连通；否则仍然连通。路径是否经过某点可以通过LCA的性质在O(logN)时间内完成判断。

预处理的Tarjan、缩点、圆方树构造、LCA预处理的总时间复杂度是O(N + M)，Q次查询的总时间复杂度是O(QlogN)，完全可以满足N≤1e5、M≤5e5、Q≤1e5的约束要求。

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