Graph Theory37 sections · 1633 units
Open in Course

Distance Query Cases

(Four scenarios)

Case 11: Both in tail. Check if yy is reachable from xx by jumping. If not, no path exists. If yes, compute distance by simulation or binary search with binary lifting. Case 22: xx in tail, yy in cycle. Jump from xx to cycle, then compute steps around cycle to yy.

Use cycle positions. Case 33: Both in cycle. Compute steps around the cycle from xx to yy using (pos[y]pos[x])modλ(\text{pos}[y] - \text{pos}[x]) \mod \lambda. Case 44: xx in cycle, yy in tail. No path exists because you cannot leave a cycle.