Can this problem done without bfs or storing edges?

Question

You are given an undirected connected graph with n nodes and n edges. Now Given two nodes a and b. find the number of edges that lies in path from a to b but are not part of cycle. (as number of edges is n there will be a cycle for sure). Can this be done by dsu data structure because if removing an edge disconnects a and b we can count it in answer. Thanks in advance.

Answer 1

Of course you can solve the problem through DSU as you mentioned, but the solution is not efficient enough. DSU is not good at deleting edges, so if you want to use DSU to solve the problem, you need to

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

Even if you implement a DSU with the path compressing and merging by rank technique, the time complexity for one query is O(n^2a(n)), where a(n) is the anti-ackermann function. It's unacceptable.

If you really want to solve the problem by enumerating and deleting edges, link cut tree is recommended which can delete or add an edge in O(logn) time. In this way, you can answer the query in O(nlogn) time.

But there do exist some really efficient algorithms which can answer each query in O(1) time if you do some preprocessing job. The graph is special: a connected graph with n vertices and n edges has only one cycle. We can regard this graph as a cycle with t vertices, each vertex is the root of a tree. So during preprocessing, we use dfs to calculate which tree each vertex is in and the depth of each vertex (in its corresponding tree, the depth of each root is 0). Besides, we use tarjan algorithm to preprocess each tree for the sake of querying LCA in O(1) time.

Then for each query, given two vertex u and v, we firstly check whether they're in the same tree. There're two situations:

• If the answer is yes, the shortest path between them is completely inside the tree so we only need to calculate the distance between u and v and obviously, the shortest distance is depth(u)+depth(v)-2*depth(LCA).
• If the answer is no, the path between u and v can be divided into 3 parts: the first part is in tree(u), the second part is on the cycle and the third part is in tree(v). In this case, the number of edges inside trees is simply depth(u)+depth(v).

By Applying the above algorithm, we can solve the problem through O(n) time complexity preprocessing and then O(1) time complexity for each query. If there're q queries and q is quite large, this algorithm will show its advantage.