Union by Size Depth

Problem

Simulate union by size and measure the resulting tree depth.

unions is a list of [a, b] pairs merged with union by size. Afterwards compute the maximum depth of any node to its root and the number of components.

Return [max_depth, components].

Hint

Attaching the smaller root under the larger keeps every tree shallow.

Test cases

case 1

in: [4,[[0,1],[2,3],[0,2]]]

expected: [2,1]

case 2

in: [3,[]]

expected: [0,3]

case 3

in: [2,[[0,1]]]

expected: [1,1]

case 4

in: [5,[[0,1],[1,2],[2,3],[3,4]]]

expected: [1,1]

Starter codePython

def union_size_depth(n, unions):
    # Your code here
    pass

4 test cases · run your code against them in the editor