Tarjan's Offline Algorithm

An Offline Approach

So far, we've explored methods that answer Lowest Common Ancestor (LCA) queries one at a time. These are called online algorithms. You can receive a query for LCA(u, v), compute the answer, and then wait for the next query.

Tarjan's algorithm takes a different approach. It's an offline algorithm, which means it requires all LCA queries to be known before it starts running. This might seem like a limitation, but in many applications, such as analyzing static datasets, you often have all your questions upfront. The trade-off is efficiency: by processing all queries in a single pass, the algorithm can be very fast.

The core idea is to answer all queries during a single Depth-First Search (DFS) traversal of the tree. To do this, it cleverly uses another data structure to keep track of which parts of the tree have been fully explored.

The Union-Find Data Structure

The key helper for Tarjan's algorithm is the Union-Find data structure, also known as a Disjoint Set Union (DSU). Its purpose is to manage a collection of items that are partitioned into a number of disjoint (non-overlapping) sets. It provides two main operations:

find(item): Determines which set an item belongs to by returning the set's representative element (or root).
union(item1, item2): Merges the two sets containing item1 and item2 into a single set.

In our case, the 'items' are the nodes of the tree. As we traverse the tree with DFS, we'll use Union-Find to group nodes into sets. Specifically, when the DFS has finished visiting all descendants of a node u, we will union u with its parent. The find operation will then tell us the highest ancestor of a node within a processed subtree.

For this to be efficient, Union-Find is often implemented with two key optimizations: path compression and union by rank/size. Together, these make the operations almost constant time on average, which is crucial for the overall performance of Tarjan's algorithm.

The Algorithm in Steps

The algorithm combines a post-order traversal (a type of DFS) with the Union-Find data structure. Here is the process:

Initialization: Initialize a Union-Find structure where each node is in its own set. For each node, also maintain a color: WHITE (unvisited), GRAY (visiting), or BLACK (visited). All nodes start as WHITE. Store the queries, grouping them by node. For a query LCA(u, v), you'll store v in a list associated with u, and u in a list associated with v.
Start DFS: Begin a DFS traversal from the root of the tree.
Process a Node u:
- Mark node u as GRAY.
- Set the ancestor of u to be u itself. The ancestor property will be maintained by the Union-Find structure; it will point to the highest node in a processed subtree.
- Recursively call DFS for each of u's children.
- After returning from the recursion for a child v, merge the sets of u and v using union(u, v). Set the ancestor of the newly merged set to u.
Check Queries: After visiting all of u's children, check all queries (u, v) associated with u. If the other node v in a query has been marked BLACK, it means the DFS has already completely finished visiting v and its entire subtree. The LCA of u and v is the representative of the set that v currently belongs to. You can find this with find(v).
Finalize Node u: Mark u as BLACK, indicating that you have finished visiting u and all of its descendants.

The magic happens in step 4. When we are at node u and look at a query (u, v), if v is already BLACK, it means v is in a different subtree that has already been fully explored. The union operations have ensured that the representative of v's set (find(v)) is the highest ancestor of v that we've processed so far. Since we haven't finished with u yet, that highest ancestor is precisely the LCA of u and v.

Implementation and Complexity

Let's look at how this can be implemented in C++. We need a way to represent the tree (like an adjacency list), store the queries, and implement the Union-Find data structure.

#include <iostream>
#include <vector>

const int MAXN = 1001;

// Tree and Query representation
std::vector<int> adj[MAXN];
std::vector<std::pair<int, int>> queries[MAXN]; // {other_node, query_index}

// Union-Find structure
int parent[MAXN];
int ancestor[MAXN];

// Visited status (color)
int color[MAXN]; // 0: WHITE, 1: GRAY, 2: BLACK

int find_set(int v) {
    if (v == parent[v])
        return v;
    return parent[v] = find_set(parent[v]);
}

void unite_sets(int a, int b) {
    a = find_set(a);
    b = find_set(b);
    if (a != b)
        parent[b] = a;
}

// Tarjan's algorithm via DFS
void tarjan_lca(int u, int p, std::vector<int>& ans) {
    parent[u] = u;
    ancestor[u] = u;
    color[u] = 1; // Mark as GRAY

    for (int v : adj[u]) {
        if (v == p) continue;
        tarjan_lca(v, u, ans);
        unite_sets(u, v);
        ancestor[find_set(u)] = u;
    }

    color[u] = 2; // Mark as BLACK

    for (auto const& [v, q_idx] : queries[u]) {
        if (color[v] == 2) { // If other node is fully visited
            ans[q_idx] = ancestor[find_set(v)];
        }
    }
}

int main() {
    // Example usage
    // Assume tree and queries are populated here
    int n = 7; // Number of nodes
    adj[1] = {2, 3};
    adj[2] = {1, 4, 5};
    adj[3] = {1, 6, 7};
    adj[4] = {2};
    adj[5] = {2};
    adj[6] = {3};
    adj[7] = {3};

    std::vector<std::pair<int, int>> query_pairs = {{4, 5}, {4, 6}, {5, 7}};
    int q_count = query_pairs.size();
    for(int i = 0; i < q_count; ++i) {
        int u = query_pairs[i].first;
        int v = query_pairs[i].second;
        queries[u].push_back({v, i});
        queries[v].push_back({u, i});
    }

    std::vector<int> ans(q_count);
    tarjan_lca(1, 0, ans);

    for (int i = 0; i < q_count; ++i) {
        std::cout << "LCA(" << query_pairs[i].first << ", " << query_pairs[i].second << ") = " << ans[i] << std::endl;
    }

    return 0;
}

The main function tarjan_lca performs the DFS. It recursively explores children, and upon returning, it unions the child's set with its own. After all children are processed, it checks its list of queries. If the other node in a query is already black, the answer is found and stored.

Metric	Complexity
Time Complexity	$O(N + Q \cdot \alpha(N))$
Space Complexity	$O(N + Q)$

Here, $N$ is the number of nodes, $Q$ is the number of queries, and $\alpha(N)$ is the inverse Ackermann function. This function grows extremely slowly, so for all practical purposes, it can be considered a small constant (less than 5). This makes the time complexity nearly linear in the number of nodes and queries.

The space complexity comes from storing the tree, the queries, and the data structures for Union-Find and colors. This makes Tarjan's algorithm a very efficient choice when all queries can be collected before processing.

Quiz Questions 1/6

What is the primary characteristic of an "offline" algorithm, such as Tarjan's algorithm for LCA?

Quiz Questions 2/6

Which data structure is essential for the implementation of Tarjan's offline LCA algorithm?

Tarjan's algorithm offers a powerful offline solution to the LCA problem, showcasing a clever combination of DFS and the Union-Find data structure to achieve near-linear time complexity.

Mastering the LCA Algorithm in C++