检查有向非循环图中两个顶点之间是否存在路径 - 查询

Question

这个问题可以在每个查询的O(n + m)中轻松解决,但是这可以通过比O(n²)更好的预处理来更好地回答这些查询吗？

在树中,可以通过预订和按顺序轻松完成.我在DAG尝试了类似的东西,但它没有任何意义.

我也尝试在DAG问题中将此问题更改为LCA,但在DAG中找到LCA无法快速解决.

---

准确地说,约束让我们说:

n - 顶点数,最多10 ^ 5

m - 边数,最多10 ^ 5

q - 查询数量,最多10 ^ 5

Answer 1

有趣的问题。我的直觉说“不”。不过我还没有想清楚。

但是（假设这个问题不是理论问题），出于实际目的，您可以使用布隆过滤器。

使用布隆过滤器解决问题的一种可能的解决方案是首先生成图表的 K 个不同顺序，并为每个顺序存储从节点到其索引的映射。然后，为了测试从 N1 到 N2 的“可达性”，您检查（针对每个订单）N1 的索引是否小于 N2 的索引（此检查的时间复杂度为 O(1)）。如果这适用于所有订单，则可以以相当好的概率到达（假设 K 足够大）。（根据您的现实世界用例，偶尔生成此类误报甚至可能是可以的，或者您可以运行可靠的 O(N+M) 检查）。不然的话，肯定不是。