图论求助

回复帖子

@3ea2c2b 2019-03-15 21:57 回复

给定一个有$n$个点的无向图$G$,图上的点$P,Q$,试判断是否存在一些点$S$,使$P$到$Q$的路径中必然经过这些点.如果有一些满足条件的点$S$,输出这些点。

我的问题是:是否有复杂度较低($< n^2$)的算法呢?

目前思路:tarjan + 枚举割点

@SSerxhs 2019-03-15 22:09 回复

广义圆方树,输出路径上所有圆点