パッケージ library.core.interfaces

インタフェース DSU

既知の実装クラスのリスト:
MergeUnionFind, UndoUnionFind, UnionFind, WeightedUnionFind

public interface DSU
UnionFindのベースとなるインターフェース Disjoint Set Union
  • メソッドの概要

    修飾子とタイプ
    メソッド
    説明
    グラフを連結成分に分け、その情報を返す
    int
    root(int i)
    頂点iの根を返す
    default boolean
    same(int i, int j)
    二頂点が同じ連結成分に所属しているかを返す
    int
    UnionFindの大きさを返す
    int
    size(int i)
    頂点iを含む連結成分のサイズ
    boolean
    unite(int i, int j)
    二頂点をマージする
  • メソッドの詳細

    • root

      int root(int i)
      頂点iの根を返す
      パラメータ:
      i -
      戻り値:
      iの根
    • size

      int size(int i)
      頂点iを含む連結成分のサイズ
      パラメータ:
      i -
      戻り値:
      iを含む連結成分のサイズ
    • size

      int size()
      UnionFindの大きさを返す
      戻り値:
      UnionFindのサイズ
    • same

      default boolean same(int i, int j)
      二頂点が同じ連結成分に所属しているかを返す
      パラメータ:
      i -
      j -
      戻り値:
      iとjが同じ連結成分に所属しているか
    • unite

      boolean unite(int i, int j)
      二頂点をマージする
      パラメータ:
      i -
      j -
      戻り値:
      未マージでtrue, マージ済でfalse
    • groups

      グラフを連結成分に分け、その情報を返す
      戻り値:
      グラフを連結成分に分けた時の状態
      関連項目: