Path Compression Rewrite Count

Problem

parent describes a disjoint-set forest where parent[i] is the parent of i and a root points to itself. Process each query index with find and full path compression: after locating the root, point every node on the path directly at it. Return the total number of parent entries rewritten, not counting nodes that already point at the root.

Hint

After the first find flattens a path, later finds over the same nodes rewrite nothing.

Test cases

case 1

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

expected: 3

case 2

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

expected: 0

case 3

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

expected: 2

case 4

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

expected: 1

Starter codePython

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

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