DSU Rollback Snapshot

Problem

Simulate a union-find with rollback snapshots.

operations contains ["union", a, b] (record True when merged), ["find", x] (record the root), ["snapshot"] (record the snapshot id), or ["rollback"] (restore the most recent snapshot and record True or False). No path compression is used, so every union can be undone through a history stack.

Return the list of recorded results.

Hint

Without path compression, each parent change is a single history entry that can be reverted.

Test cases

case 1

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

expected: [true,0,true,0,true,2]

case 2

in: [2,[["rollback"]]]

expected: [false]

case 3

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

expected: [true,false,0]

case 4

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

expected: [true,0,true,true,3]

Starter codePython

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

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