混合图中判断节点双向可达并统计符合要求节点数量的方法是什么

前置处理：混合图转纯有向图 #

所有无向边等价于两条方向相反的有向边，直接把每条无向边(u, v)拆成u→v和v→u两条有向边，就可以把混合图转换为纯有向图处理，转换后可达性规则和原图完全一致。

问题1：判断节点A、B是否双向可达 #

根据查询次数选择对应方案：

• 单次查询：直接执行两次BFS/DFS即可，第一次从A出发遍历所有可达节点，验证B是否在可达集合中；第二次从B出发遍历所有可达节点，验证A是否在可达集合中，两次都满足即双向可达，时间复杂度为O(N+E)（N为节点数，E为边数）。
• 多次查询：提前计算全图的强连通分量（SCC），给每个节点标记所属的SCC编号，只要A和B的SCC编号相同，就说明二者双向可达，单次查询时间复杂度为O(1)。

问题2：统计满足双向可达条件的节点总数 #

根据统计需求选择对应方案：

• 统计与指定节点A双向可达的节点总数：直接取A所在SCC的大小即可，也可以分别对原图、反图从A出发执行BFS/DFS，两次遍历结果的交集大小就是答案，时间复杂度O(N+E)。
• 统计全图所有两两双向可达的节点集合总规模：计算全图所有SCC的大小，根据实际需求输出对应值即可，比如输出最大SCC的大小、所有大小≥2的SCC的节点总和、所有SCC的大小列表。

常用强连通分量计算算法 #

两者时间复杂度均为O(N+E)，适合大规模图计算：

• Kosaraju算法：实现逻辑简单不易出错，先对原图跑DFS按节点完成时间压栈，再构建反图按栈的出栈顺序跑DFS，每次遍历到的节点就是一个SCC。
• Tarjan算法：单次DFS即可完成计算，不需要额外构建反图，空间效率更高。

小规模图简化方案 #

如果节点规模N≤1000，可以直接用Floyd算法预处理传递闭包，得到可达性矩阵d[i][j]（表示i是否可以到达j），后续判断双向可达只要验证d[A][B] && d[B][A]即可，统计总数直接遍历所有节点对统计符合条件的结果，时间复杂度为O(N³)。

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