DSU Persistent Parent Versions

Problem

Simulate a persistent union-find whose parent arrays are versioned.

operations contains ["union", version, a, b] (creates a new version and records its id), ["find", version, x] (records the root), or ["parents", version] (records the parent array). Union by size is used and old versions never change.

Return the list of recorded results.

Hint

Copying the referenced version before mutating keeps every older version immutable.

Test cases

case 1

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

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

case 2

in: [1,[["parents",0]]]

expected: [[0]]

case 3

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

expected: [1,[0,1],[0,0]]

case 4

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

expected: [1]

Starter codePython

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

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