0

给定一个具有n 个节点和n 个边的无向连通图。现在给定两个节点a和b。找到从 a 到 b 的路径中但不属于循环的边数。（因为边数是 n 肯定会有一个循环）。这可以通过 dsu 数据结构来完成吗，因为如果删除一条边断开 a 和 b 我们可以在答案中计算它。提前致谢。

4

1 回答 1

1

当然你可以通过你提到的DSU解决问题，但是解决方案不够高效。DSU不擅长删除边，所以如果要使用DSU解决问题，需要

for e in E
   use E-e to construct a DSU
   check the connectivity of a and b

即使您使用按秩技术进行路径压缩和合并的 DSU 实现，一个查询的时间复杂度也是 O(n^2a(n))，其中 a(n) 是反阿克曼函数。这是不可接受的。

如果你真的想通过枚举和删除边来解决问题，推荐使用链接切割树，它可以在 O(logn) 时间内删除或添加边。这样，您可以在 O(nlogn) 时间内回答查询。

但是确实存在一些非常有效的算法，如果你做一些预处理工作，它们可以在 O(1) 时间内回答每个查询。该图很特殊：具有n个顶点和n条边的连通图只有一个循环。我们可以把这个图看成一个有 t 个顶点的环，每个顶点都是一棵树的根。所以在预处理的时候，我们使用dfs来计算每个顶点在哪棵树以及每个顶点的深度（在其对应的树中，每个根的深度为0）。此外，我们使用 tarjan 算法对每棵树进行预处理，以便在 O(1) 时间内查询 LCA。

然后对于每个查询，给定两个顶点u和v，我们首先检查它们是否在同一棵树中。有两种情况：

  • 如果答案是肯定的，那么它们之间的最短路径完全在树内，所以我们只需要计算和之间的距离u，v显然，最短距离是depth(u)+depth(v)-2*depth(LCA)。
  • u如果答案是否定的，则和之间的路径v可以分为3部分：第一部分在tree(u)中，第二部分在循环上，第三部分在tree(v)中。在这种情况下，树内的边数只是深度（u）+深度（v）。

通过应用上述算法，我们可以通过 O(n) 时间复杂度预处理和每个查询的 O(1) 时间复杂度来解决问题。如果有q查询并且q很大，这个算法就会显示出它的优势。

于 2021-08-25T09:09:09.247 回答