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

Question

这个问题可以很容易地在每个查询的 O(n + m) 中解决，但是，是否可以通过比 O(n²) 更好的预处理以更复杂的方式回答此类查询？

在树中，可以通过使用预序和顺序轻松完成。我在 DAG 中尝试过类似的东西，但没有任何意义。

我也试过把这个问题改成DAG中的LCA问题，但是在DAG中寻找LCA的速度不够快。

---

准确地说，约束是这样的:

n - 顶点数，最多 10^5

m - 边数，最多 10^5

q - 查询数，最多 10^5

Answer 1

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

但是(假设这个问题不是理论问题)，出于实际目的，您可以使用 Bloom filter .

使用 Bloom 过滤器解决您的问题的一个可能解决方案是首先生成 K 个不同顺序的图，并为每个顺序存储从节点到其索引的映射。然后，为了测试从 N1 到 N2 的“可达性”，您检查 (foreach order) N1 的索引是否小于 N2 的索引(此检查为 O(1))。如果这适用于所有订单，则很有可能到达 ( assuming K is big enough )。 (根据您的实际用例，偶尔生成此类误报甚至可能没问题，或者您可以运行可靠的 O(N+M) 检查)。否则，肯定不是。