Tarjan's lowest common ancestor algorithm explanation

Question

I am having a tough time understanding Tarjan's lowest common ancestor algorithm. Can somebody explain it with an example?

I am stuck after the DFS search, what exactly does the algorithm do?

Answer 1

My explanation will be based on the wikipedia link posted above :).

I assumed that you already know about the union disjoint structure using in the algorithm. (If not please read about it, you can find it in "Introduction to Algorithm").

The basic idea is every times the algorithm visit a node x, the ancestor of all its descendants will be that node x.

So to find a Least common ancestor (LCA) r of two nodes (u,v), there will be two cases:

• Node u is a child of node v (vice versa), this case is obvious.

• Node u is ith branch and v is the jth branch (i < j) of node r, so after visit node u, the algorithm backtrack to node r, which is the ancestor of the two nodes, mark the ancestor of node u as r and go to visit node v. At the moment it visit node v, as u is already marked as visited (black), so the answer will be r. Hope you get it!