network/union_find library

🔗 Union-Find / Disjoint Set Data Structure

A highly efficient data structure for managing a collection of disjoint sets with fast union and find operations. Implements path compression and union by rank for optimal performance.

  • Time Complexity:
    • Find: O(α(n)) amortized (inverse Ackermann function)
    • Union: O(α(n)) amortized
    • MakeSet: O(1)
  • Space Complexity: O(n) where n is the number of elements
  • Optimality: Near-constant time complexity in practice
  • Applications: Network connectivity, Kruskal's MST, image processing

The data structure uses path compression and union by rank to achieve near-constant time complexity for all operations.

Example:

final uf = UnionFind<String>();
uf.makeSet('A');
uf.makeSet('B');
uf.makeSet('C');

uf.union('A', 'B');
print(uf.find('A') == uf.find('B')); // true
print(uf.find('A') == uf.find('C')); // false

uf.union('B', 'C');
print(uf.find('A') == uf.find('C')); // true

Classes

UnionFind<T>
Union-Find / Disjoint Set data structure implementation
UnionFindDetailed<T>
Enhanced Union-Find with detailed statistics and analysis
UnionFindNode<T>
Represents a node in the Union-Find data structure