Intermediate

Union-Find (or Disjoint Set) is a data structure used to manage disjoint sets of elements through two primary operations: find(x) and union(A, B). The find(x) operation determines which set the element $x$ belongs to, while the union(A, B, C) operation merges the sets $A$ and $B$ into a single set $C$. In this article, we will explore Robert Endre Tarjan’s work on determining the upper bound of the time complexity for these Union-Find operations.