Past exam of the year 1 of the computer science course of the University of Oxford / 2016 / Functional programming, design and analysis of algorithms (resit) / 5 / d / Solution

A disjoint-set data structure maintains a partition of a set into pairwise disjoint sets. Make-Set(v) creates the singleton containing a new vertex. Find-Set(v) returns the disjoint-set representative of its current set. Union(u,v) merges the two sets containing its arguments, preserving the partition; it has no effect if they are already the same set. A disjoint-set forest can implement these operations without explicitly moving every member when sets are joined.