In the depth-determination problem, we maintain a forest F = {T_i} of rooted trees under three operations:

MAKE-TREE (ν) creates a tree whose only node is ν.

FIND-DEPTH (ν) returns the depth of node ν within its tree.

GRAFT (r, ν) makes node r, which is assumed to be the root of a tree, become the child of node ν, which is assumed to be in a different tree than r but may or may not itself be a root.

a. Suppose that we use a tree representation similar to a disjoint-set forest: ν.p is the parent of node ν, except that ν.p = ν if ν is a root. Suppose further that we implement GRAFT (r, ν) by setting r.p = ν and FIND-DEPTH (ν) by following the find path up to the root, returning a count of all nodes other than ν

encountered. Show that the worst-case running time of a sequence of m MAKE-TREE, FIND-DEPTH, and GRAFT operations is Θ(m²).

By using the union-by-rank and path-compression heuristics, we can reduce the worst-case running time. We use the disjoint-set forest S = {S_i}, where each set S_i (which is itself a tree) corresponds to a tree T_i in the forest F. The tree structure within a set S_i, however, does not necessarily correspond to that of T_i. In fact, the implementation of Si does not record the exact parent-child relationships but nevertheless allows us to determine any node's depth in T_i.

The key idea is to maintain in each node ν a "pseudodistance" ν.d, which is defined so that the sum of the pseudodistances along the simple path from ν to the root of its set S_i equals the depth of ν in Ti. That is, if the simple path from ν to its root in S_i is ν′, ν₁, . . . ,ν_k, where ν′ = ν and ν_k is S_i ’s root, then the depth of ν in Ti is ∑^k_j=0 ν_j.d.

b. Give an implementation of MAKE-TREE.

c. Show how to modify FIND-SET to implement FIND-DEPTH. Your implementation should perform path compression, and its running time should be linear in the length of the find path. Make sure that your implementation updates pseudodistances correctly.

d. Show how to implement GRAFT(r, ν), which combines the sets containing r and ν, by modifying the UNION and LINK procedures. Make sure that your implementation updates pseudodistances correctly. Note that the root of a set S_i is not necessarily the root of the corresponding tree T_i.

e. Give a tight bound on the worst-case running time of a sequence of m MAKETR GRAFT operations, n of which are MAKE-TREE operations.