Overview
DSU, also known as Union-Find, manages a collection of disjoint sets. Each set is represented by a representative element called its root. The structure is especially useful when relationships between elements change through repeated merge operations.
How it works
Initially, every element belongs to its own individual set.; Each set has a representative or root element.; The Find operation identifies the representative of an element's set.; The Union operation combines the sets containing two specified elements.; After merging, both sets share the same representative.
Key concepts
Disjoint sets; Set representatives; Parent arrays; Find operation; Union operation; Dynamic connectivity
Time complexity
operation: MakeSet; complexity: O(1); operation: Find; complexity: O(n) in the worst case without optimizations; operation: Union; complexity: Depends on the implementation of Find and the merging strategy
Space complexity
O(n), where n is the number of elements.
Example
description: Consider five elements: 1, 2, 3, 4, and 5.; operations: Initially: {1}, {2}, {3}, {4}, {5}; Union(1, 2): {1, 2}, {3}, {4}, {5}; result: Elements 1, 2, 3, and 4 belong to the same set, while element 5 remains separate.
Applications
Connected-component detection; Kruskal's minimum spanning tree algorithm; Network connectivity; Grouping related objects; Cycle detection in undirected graphs