DSU Rollback History Size

Problem

Run a union-find with union by size, no path compression, and a history stack. operations contains ["union", a, b], which pushes one entry when it merges two components, or ["rollback"], which undoes the most recent union when the history is non-empty. Return [log_size, component_count] after all operations.

Hint

Store the old parent and the old size of the winning root so a rollback restores both exactly.

Test cases

case 1

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

expected: [0,4]

case 2

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

expected: [0,3]

case 3

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

expected: [2,3]

Starter codePython

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

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