Class UnionFind<V>

java.lang.Object
cloud.opencode.base.graph.algorithm.UnionFind<V>
Type Parameters:
V - the vertex type | 顶点类型
public class UnionFind<V> extends Object
Union-Find (Disjoint Set) data structure with path compression and union by rank. 并查集（不相交集合）数据结构，支持路径压缩和按秩合并。

Provides efficient operations for tracking connected components in a graph. Uses path compression during find operations and union by rank to keep the tree flat, achieving near-constant amortized time complexity for both find and union.

提供高效的操作来跟踪图中的连通分量。在查找操作中使用路径压缩， 在合并操作中使用按秩合并来保持树的扁平化，从而实现近常数的均摊时间复杂度。

Features | 主要功能:

  • Path compression for near O(1) find - 路径压缩实现近O(1)查找
  • Union by rank for balanced trees - 按秩合并保持树平衡
  • Component count tracking - 连通分量计数跟踪
  • Component enumeration - 连通分量枚举

Usage Examples | 使用示例:

UnionFind<String> uf = new UnionFind<>(List.of("A", "B", "C", "D"));
uf.union("A", "B");
uf.union("C", "D");
boolean same = uf.connected("A", "B"); // true
int count = uf.componentCount();        // 2
Set<String> comp = uf.componentOf("A"); // {"A", "B"}
Since:
JDK 25, opencode-base-graph V1.0.3
Author:
Leon Soo www.LeonSoo.com
See Also:

  • Constructor Summary

    Constructors
    Constructor
    Description
    UnionFind(Collection<V> elements)
    Create a UnionFind with the given elements, each in its own singleton set.

  • Method Summary

    Modifier and Type
    Method
    Description
    int
    componentCount()
    Get the number of distinct components.
    Set<V>
    componentOf(V element)
    Get all elements in the same component as the given element.
    List<Set<V>>
    components()
    Get all components as a list of sets.
    boolean
    connected(V a, V b)
    Check if two elements are in the same component.
    V
    find(V element)
    Find the representative (root) of the set containing the given element, with path compression.
    boolean
    union(V a, V b)
    Union the sets containing elements a and b using union by rank.

    Methods inherited from class Object

    clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

  • Constructor Details

    • UnionFind

      public UnionFind(Collection<V> elements)
      Create a UnionFind with the given elements, each in its own singleton set. 使用给定元素创建并查集，每个元素初始为独立的单元素集合。
      Parameters:
      elements - the initial elements | 初始元素集合
      Throws:
      IllegalArgumentException - if elements is null or contains null elements | 当elements为null或包含null元素时抛出

  • Method Details

    • find

      public V find(V element)
      Find the representative (root) of the set containing the given element, with path compression. 查找包含给定元素的集合的代表元素（根），使用路径压缩。
      Parameters:
      element - the element to find | 要查找的元素
      Returns:
      the representative of the set | 集合的代表元素
      Throws:
      IllegalArgumentException - if element is null or not in the UnionFind | 当元素为null或不在并查集中时抛出

    • union

      public boolean union(V a, V b)
      Union the sets containing elements a and b using union by rank. 使用按秩合并将包含元素a和b的集合合并。
      Parameters:
      a - the first element | 第一个元素
      b - the second element | 第二个元素
      Returns:
      true if the two elements were in different sets and have been merged, false if they were already in the same set | 如果两个元素在不同集合中并已合并则返回true，如果已在同一集合中则返回false
      Throws:
      IllegalArgumentException - if a or b is null or not in the UnionFind | 当a或b为null或不在并查集中时抛出

    • connected

      public boolean connected(V a, V b)
      Check if two elements are in the same component. 检查两个元素是否在同一个连通分量中。
      Parameters:
      a - the first element | 第一个元素
      b - the second element | 第二个元素
      Returns:
      true if a and b are in the same component | 如果a和b在同一连通分量中则返回true
      Throws:
      IllegalArgumentException - if a or b is null or not in the UnionFind | 当a或b为null或不在并查集中时抛出

    • componentCount

      public int componentCount()
      Get the number of distinct components. 获取不同连通分量的数量。
      Returns:
      the number of components | 连通分量的数量

    • componentOf

      public Set<V> componentOf(V element)
      Get all elements in the same component as the given element. 获取与给定元素在同一连通分量中的所有元素。
      Parameters:
      element - the element | 元素
      Returns:
      an unmodifiable set of all elements in the same component | 包含同一连通分量中所有元素的不可修改集合
      Throws:
      IllegalArgumentException - if element is null or not in the UnionFind | 当元素为null或不在并查集中时抛出

    • components

      public List<Set<V>> components()
      Get all components as a list of sets. 获取所有连通分量，以集合列表的形式返回。
      Returns:
      a list of all components, each represented as an unmodifiable set | 所有连通分量的列表，每个分量为不可修改的集合