19. Data Structures for Disjoint Sets

Exercises

19.1-1

Use the Data Structure Visualizations tool that preinitializes 16 disjoint sets as a starting point. Each member is denoted by an integer. For this example, just assign zero based indices to vertices. For example, 'a' would be represented with 0, 'b' with 1, etc. You would only use the first 11 elements (0..10). To process an edge convert vertices to indices. For example, the first edge $(d,i)$ would be a union between 3 and 8. You should end up with 3 disjoint sets (notice that 2 ('c') is a singleton set).

19.1-2

Available in the latest revision of the IM.

19.1-3

Available in the latest revision of the IM.

19.2-1

Available in the latest revision of the IM.

19.2-2

Available in the latest revision of the IM.

19.2-3

Available in the latest revision of the IM.

19.2-4

Available in the latest revision of the IM.

19.2-5

Available in the latest revision of the IM.

The IM solution fundamentally breaks down during a UNION operation. If x.rep points directly to the tail element, then whenever a set absorbs another set, its tail changes. To prevent stale pointers, you would have to update the x.rep pointer for every single element in the absorbing set. Furthermore, the IM's final claim that a pointer to "any list element would suffice" is incorrect, too.

Instead of x.rep the system should still rely on x.set and route things through a stable set object. The tail's next pointer can be reused to point back to the head of the list.

19.2-6

Available in the latest revision of the IM.

19.3-1

Available in the latest revision of the IM.

19.3-2

Available in the latest revision of the IM.

19.3-3

Available in the latest revision of the IM.

19.3-4 🌟

Demonstrates the advantages of crafting hybrid data structures. In this case, the disjoint-set forest is combined with an underlying circular singly linked list to expedite printing members of a set.

Available in the latest revision of the IM.

★ 19.3-5

Available in the latest revision of the IM.

The worst-case $O(m \alpha(n))$ bound in the standard disjoint-set forest (see Section 19.4) happens specifically because we can alternate between operations. We can flatten a tall tree using FIND-SET, and then immediately "bury" that newly flattened tree by using a LINK to attach its root to an even taller tree. By constantly mixing LINK and FIND-SET, we force the algorithm to repeatedly traverse and re-compress paths that keep growing.

When we front-load all the LINK operations, we completely remove the ability to "bury" nodes. This is exactly how that brings the time bound down to strictly $O(m)$:

19.4-1

Available in the latest revision of the IM.

19.4-2

Available in the latest revision of the IM.

There is a simpler proof. After proving the claim that for all tree roots $x$, we have $x.size \ge 2^{x.rank}$, it immediately follows that $n \ge x.size \implies x.rank \le \lg n \implies x.rank \le \rfloor \lg n \rfloor$.

19.4-3

Available in the latest revision of the IM.

19.4-4

Available in the latest revision of the IM.

19.4-5

Available in the latest revision of the IM.

19.4-6

Available in the latest revision of the IM.

★ 19.4-7

Available in the latest revision of the IM.

Problems

19-1 Offline minimum

Available in the latest revision of the IM.

19-2 Depth determination

Available in the latest revision of the IM.

19-3 Tarjan’s offline lowest-common-ancestors algorithm

a.

The LCA procedure executes a depth-first search traversal of the rooted tree $T$. Consequently, each node is visited exactly once, and any given pair is examined only twice, once in each direction. During the first examination, the other element of the pair is still WHITE (not yet visited). Only upon the second examination are both elements colored BLACK, at which point their lowest common ancestor is printed.

b.

This follows from the DFS traversal. Lines 1–2 create a singleton set before recursing into any children. Children at the same level, sharing a parent, are processed sequentially. Line 5 merges each child’s set with the parent’s set before the next child is processed; therefore, the number of sets remains fixed throughout the level.

Because siblings are merged and only the nodes on the active DFS path remain unmerged, the only existing sets correspond exactly to $u$ and its ancestors. By definition, the number of ancestors is the depth of $u$.

c.

At the exact moment LCA(u) is evaluating the pairs, the tree is divided into disjoint sets. For any fully processed (BLACK) node $v$, FIND-SET(v).ancestor points to the lowest node on the current active recursion stack that is an ancestor of $v$. Because node $u$ is the one currently being processed, the active recursion stack consists perfectly of $u$ and all of its ancestors. Therefore, the lowest node on the stack that is also an ancestor of $v$ is, by definition, the lowest common ancestor of $u$ and $v$.

Let $w$ be the lowest common ancestor of $u$ and $v$. Because line 10 only triggers when $u$ is currently executing and $v$ is already BLACK, we know $w$ finished its execution before $u$.

This leaves exactly two possible structural scenarios:

Scenario 1: $v$ is a proper descendant of $u$ In this case, the lowest common ancestor is $u$ itself ($w = u$).

• Because $v$ is a descendant, the DFS traveled down from $u$ into one of its child branches and completely processed $v$.

• As the recursion unspooled back up that branch toward $u$, line 5 (UNION) continuously merged the child sets into the parent sets.

• Line 6 immediately reset the ancestor pointer of those newly merged sets to the parent.

• Because we are currently inside LCA(u), the child branch containing $v$ has just finished. The set containing $v$ has been merged into $u$'s set, and its ancestor has been set to $u$.

• Thus, FIND-SET(v).ancestor correctly returns $u$.

Scenario 2: $u$ and $v$ are in different branches of $w$ In this case, $w$ sits somewhere above $u$.

• The DFS reached $w$ first, then traveled down one child's branch and completely processed $v$ (coloring it BLACK).

• The recursion returned to $w$. At this moment, line 5 merged the entire branch containing $v$ into $w$'s set, and line 6 explicitly set the ancestor of that combined set to $w$.

• The DFS then moved to a different child of $w$ and traveled down until it reached $u$.

• While we are evaluating pairs inside LCA(u), the recursive call LCA(w) is still active on the stack waiting for $u$'s branch to finish. Because $w$ has not finished, it has not yet been merged into its own parent.

• Therefore, the highest union that $v$ has participated in stopped exactly at $w$.

• Thus, FIND-SET(v).ancestor correctly returns $w$.

d.

We have a sequence of $|T|+|P|$ disjoint-set operations resulting in $O((|T|+|P|)\alpha(|T|))$ time. This dominates the overall running time, since the rest of the DFS traversal takes less time.