Overview
Tarjan's offline LCA processes all queries together, merging completed subtrees with union-find so each query can be answered when both endpoints have been visited.
ExtendedSource checked
Tarjan's Offline LCA
Answers lowest-common-ancestor queries in a tree using DFS and union-find.
Quick Facts
Compact metadata for implementation and discovery.
- Category
- Graph Traversal
- Difficulty
- Advanced
- Family
- Offline Tree Queries
- Tier
- Extended
- Status
- Verified
- Review
- Source Checked
- Sources
- 2
- Formulas
- 1
- Relationships
- 1
- Code example
- Ready
- Visualization
- Ready
Core Concepts
offline queryunion-findtree dfsancestor label
Quick facts
Complexity
Runtime and memory behavior at a glance.
Best
O((n + q) alpha(n))
Average
O((n + q) alpha(n))
Worst
O((n + q) alpha(n))
Space
O(n + q)
When to Use
- Use when analyzing graph structure needs offline query.
- Use when the input matches the assumptions behind offline Tree Queries.
When Not to Use
- Avoid when the graph is so large that it needs streaming or external-memory handling.
- Avoid when a simpler algorithm gives the required result with less setup.
What It Does
- Answers lowest-common-ancestor queries in a tree using DFS and union-find
- Uses offline query and union-find to guide the work.
- Produces visited nodes.
Use Cases
- Analyzing graph structure
- Finding connectivity patterns
- Preparing graph-derived orderings
Inputs
- Graph
- Start nodes or query nodes
- Traversal state
Outputs
- Visited nodes
- Derived graph relationships
Key Formulas (1)
Union-find representative
ancestor[find(v)] = currentancestor
ancestor[find(v)] = current_ancestorStores the current ancestor for each completed union-find set.
Pseudocode
- 1.Prepare the inputs and state needed for Tarjan's Offline LCA.
- 2.Apply the offline query step while the stopping condition has not been met.
- 3.Update intermediate state and discard invalid candidates.
- 4.Return visited nodes.
Canonical Example
- Input
- Tarjan's Offline LCA input with a small representative case
- Output
- Visited nodes
- Explanation
- Tarjan's Offline LCA applies offline query to produce visited nodes.
Implementation Notes
- Keep visitation state and edge classification state separate.
- Keep the offline query step separate enough to test independently.
Common Pitfalls
- Mixing directed and undirected edge assumptions can produce incorrect graph relationships.
- Forgetting to check edge cases can make Tarjan's Offline LCA look correct on only ideal inputs.
Interactive Mechanism Walkthrough
Graph Frontier & Edge RelaxationHighlight active nodes, discovered edges, and the graph structure produced by each step.
Step 1 of 4: Prepare the inputs and state needed for Tarjan's Offline LCA.
graph-traversal-mechanismNotes
Tarjan's Offline LCA should be used with the assumptions and tradeoffs of offline Tree Queries in mind.
Sources (2)
What each reference supports for this entry.
Introduction to Algorithms (CLRS)
BookTextbook support for Tarjan's Offline LCA's standard algorithm design, invariants, and complexity analysis.
Open sourceThe Algorithm Design Manual
BookAlgorithm catalog support for Tarjan's Offline LCA's problem context, known alternatives, and practical selection tradeoffs.
Open sourceExplore Next
Good next jumps from the relationship graph, ranked for useful discovery.
Relationships
View full relationship pageUsesUnion-Find
Tarjan's offline LCA answers ancestor queries by combining DFS traversal with union-find sets.
Related Algorithms
Tags
TreeLCAUnion FindOffline Query