パッケージ library.ds.unionfind

クラス UnionFind

java.lang.Object
library.ds.unionfind.UnionFind
すべての実装されたインタフェース:
DSU
直系の既知のサブクラス:
MergeUnionFind
public class UnionFind extends Object implements DSU
UnionFind

  • フィールドの概要

    フィールド
    修飾子とタイプ
    フィールド
    説明
    protected final int[]
    par
     

  • コンストラクタの概要

    コンストラクタ
    コンストラクタ
    説明
    UnionFind(int n)
    コンストラクタ

  • メソッドの概要

    修飾子とタイプ
    メソッド
    説明
    final ArrayList<ArrayList<Integer>>
    groups()
    グラフを連結成分に分け、その情報を返す
    final int
    root(int i)
    頂点iの根を返す
    final int
    size()
    UnionFindの大きさを返す
    final int
    size(int i)
    頂点iを含む連結成分のサイズ
    final String
    toString()
     
    boolean
    unite(int i, int j)
    二頂点をマージする

    クラスから継承されたメソッド java.lang.Object

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

    インタフェースから継承されたメソッド library.core.interfaces.DSU

    same

  • フィールド詳細

    • par

      protected final int[] par

  • コンストラクタの詳細

    • UnionFind

      public UnionFind(int n)
      コンストラクタ
      パラメータ:
      n - サイズ

  • メソッドの詳細

    • root

      public final int root(int i)
      インタフェースからコピーされた説明: DSU
      頂点iの根を返す
      定義:
      root インタフェース内 DSU
      パラメータ:
      i -
      戻り値:
      iの根

    • size

      public final int size(int i)
      インタフェースからコピーされた説明: DSU
      頂点iを含む連結成分のサイズ
      定義:
      size インタフェース内 DSU
      パラメータ:
      i -
      戻り値:
      iを含む連結成分のサイズ

    • size

      public final int size()
      インタフェースからコピーされた説明: DSU
      UnionFindの大きさを返す
      定義:
      size インタフェース内 DSU
      戻り値:
      UnionFindのサイズ

    • unite

      public boolean unite(int i, int j)
      インタフェースからコピーされた説明: DSU
      二頂点をマージする
      定義:
      unite インタフェース内 DSU
      パラメータ:
      i -
      j -
      戻り値:
      未マージでtrue, マージ済でfalse

    • groups

      public final ArrayList<ArrayList<Integer>> groups()
      インタフェースからコピーされた説明: DSU
      グラフを連結成分に分け、その情報を返す
      定義:
      groups インタフェース内 DSU
      戻り値:
      グラフを連結成分に分けた時の状態
      関連項目:

    • toString

      public final String toString()
      オーバーライド:
      toString クラス内 Object