findset

Findset, in the context of disjoint-set union (DSU) data structures, is the operation that locates the representative element (the set leader) of the set containing a given item. It is commonly implemented as a function named find_set or find and is often used together with the union operation to merge sets.

DSU maintains a collection of disjoint sets over a finite universe of elements. Each element points to a parent, forming a forest of trees. The representative of a set is the root of its tree. The findset operation traverses parent pointers from a given element up to the root, returning the root as the set’s representative. Path compression is usually applied during this traversal, updating visited nodes to point directly to the root, which flattens the tree and speeds up future operations.

The primary purpose of findset is to support efficient queries about connectivity: two elements are in the same set if their findset results are equal. When paired with union (which merges two sets, typically by size or rank to keep trees shallow), DSU enables near-constant-time performance in many applications.

Common uses include Kruskal’s algorithm for minimum spanning trees, dynamic connectivity problems, network design, and various computational geometry and image processing tasks. The combination of path compression and union by size or rank yields an amortized time complexity per operation that is effectively constant, often expressed as O(alpha(n)), where alpha is the inverse Ackermann function.

In practice, findset is often implemented as FindSet, find_set, or simply Find, and the exact naming may vary by library or programming language.