这个问题可以在没有 bfs 或存储边缘的情况下完成吗？
Can this problem done without bfs or storing edges?
给你一个无向连通图，有n个节点和n个边。现在给定两个节点 a 和 b。找到位于从 a 到 b 的路径中但不属于循环的边的数量。
（因为边数是 n 肯定会有一个循环）。这可以通过 dsu 数据结构来完成，因为如果删除边断开 a 和 b 我们可以在答案中计算它。提前致谢。
当然可以像你说的那样通过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) 是反阿克曼函数。这是不可接受的。
如果你真的想通过枚举和删除边来解决问题，建议使用link cut tree，它可以在O(logn)时间内删除或添加一条边。这样，您可以在 O(nlogn) 时间内回答查询。
但是确实存在一些非常有效的算法，如果您进行一些预处理工作，它们可以在 O(1) 时间内回答每个查询。该图很特殊：具有n个顶点和n条边的连通图只有一个圈。我们可以把这个图看成一个有t个顶点的环，每个顶点都是一棵树的根。所以在预处理时，我们使用dfs计算每个顶点在哪棵树中，以及每个顶点的深度（在其对应的树中，每个根的深度为0）。此外，为了在O(1)时间内查询LCA，我们使用tarjan算法对每棵树进行预处理。
然后对于每个查询，给定两个顶点 u 和 v，我们首先检查它们是否在同一棵树中。有两种情况：
- 如果答案是肯定的，它们之间的最短路径完全在树内部，所以我们只需要计算
u和v之间的距离，显然，最短距离是深度（ u)+深度(v)-2*深度(LCA).
- 如果答案是否定的，
u和v之间的路径可以分为3部分：第一部分在tree(u)上，第二部分在循环上，第三部分在 tree(v) 中。在这种情况下，树内边的数量就是 depth(u)+depth(v).
应用上面的算法，我们可以通过O(n)时间复杂度的预处理，然后每个查询的O(1)时间复杂度来解决问题。如果有 q 个查询，并且 q 相当大，这个算法将显示它的优势。
给你一个无向连通图，有n个节点和n个边。现在给定两个节点 a 和 b。找到位于从 a 到 b 的路径中但不属于循环的边的数量。 （因为边数是 n 肯定会有一个循环）。这可以通过 dsu 数据结构来完成，因为如果删除边断开 a 和 b 我们可以在答案中计算它。提前致谢。
当然可以像你说的那样通过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) 是反阿克曼函数。这是不可接受的。
如果你真的想通过枚举和删除边来解决问题，建议使用link cut tree，它可以在O(logn)时间内删除或添加一条边。这样，您可以在 O(nlogn) 时间内回答查询。
但是确实存在一些非常有效的算法，如果您进行一些预处理工作，它们可以在 O(1) 时间内回答每个查询。该图很特殊：具有n个顶点和n条边的连通图只有一个圈。我们可以把这个图看成一个有t个顶点的环，每个顶点都是一棵树的根。所以在预处理时，我们使用dfs计算每个顶点在哪棵树中，以及每个顶点的深度（在其对应的树中，每个根的深度为0）。此外，为了在O(1)时间内查询LCA，我们使用tarjan算法对每棵树进行预处理。
然后对于每个查询，给定两个顶点 u 和 v，我们首先检查它们是否在同一棵树中。有两种情况：
- 如果答案是肯定的，它们之间的最短路径完全在树内部，所以我们只需要计算
u和v之间的距离，显然，最短距离是深度（ u)+深度(v)-2*深度(LCA). - 如果答案是否定的，
u和v之间的路径可以分为3部分：第一部分在tree(u)上，第二部分在循环上，第三部分在 tree(v) 中。在这种情况下，树内边的数量就是 depth(u)+depth(v).
应用上面的算法，我们可以通过O(n)时间复杂度的预处理，然后每个查询的O(1)时间复杂度来解决问题。如果有 q 个查询，并且 q 相当大，这个算法将显示它的优势。