Union-Find Union by Rank

Problem

Simulate a union-find (disjoint set) structure with union by rank and path halving.

operations is a list of ["union", a, b] or ["find", x] commands. A union records True when it merged two different components and False when they were already connected; find records the root of x. Nodes are numbered 0 to n-1 and start in separate components.

Return the list of recorded results.

Hint

Attach the smaller-rank root under the larger one; equal ranks bump the winner's rank.

Test cases

case 1

in: [5,[["union",0,1],["find",0],["find",1],["union",1,2],["find",0],["union",0,1]]]

expected: [true,0,0,true,0,false]

case 2

in: [3,[["union",0,1],["union",1,2],["find",2],["find",0]]]

expected: [true,true,0,0]

case 3

in: [2,[["find",0],["find",1],["union",0,1],["find",1]]]

expected: [0,1,true,0]

case 4

in: [4,[["union",3,2],["union",1,0],["union",2,0],["find",3]]]

expected: [true,true,true,3]

Starter codePython

def uf_union(n, operations):
    # Your code here
    pass

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