Union-Find Find with Path Compression

Problem

Answer connectivity queries while applying path compression.

parent is a list where parent[i] is the parent of i in a disjoint-set forest (a root points to itself). For each index in queries, find its root and compress the path so future lookups are shorter.

Return the list of roots, one per query.

Hint

First walk to the root, then walk again pointing every node on the path at it.

Test cases

case 1

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

expected: [0,0,0,0]

case 2

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

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

case 3

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

expected: [0,0,0]

case 4

in: [[0],[0,0]]

expected: [0,0]

Starter codePython

def uf_find(parent, queries):
    # Your code here
    pass

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