パッケージ library.ds.unionfind

クラス WeightedUnionFind

java.lang.Object
library.ds.unionfind.WeightedUnionFind
すべての実装されたインタフェース:
DSU
public final class WeightedUnionFind extends Object implements DSU
重みつきUnionFind(PotentialつきUnionFind)
関連項目:

  • コンストラクタの概要

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

  • メソッドの概要

    修飾子とタイプ
    メソッド
    説明
    final long
    diff(int x, int y)
    二頂点の根の重みの差を返す
    final long
    get(int i)
    iの根の重みを返す
    final ArrayList<ArrayList<Integer>>
    groups()
    グラフを連結成分に分け、その情報を返す
    final int
    root(int i)
    頂点iの根を返す
    final int
    size()
    UnionFindの大きさを返す
    final int
    size(int i)
    頂点iを含む連結成分のサイズ
    final String
    toString()
     
    final boolean
    unite(int i, int j)
    推奨されていません。
    インターフェースで仕方なく適当に実装
    final int
    unite(int x, int y, long w)
    xとyをマージする

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

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

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

    same

  • コンストラクタの詳細

    • WeightedUnionFind

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

  • メソッドの詳細

    • root

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

    • get

      public final long get(int i)
      iの根の重みを返す
      パラメータ:
      i -
      戻り値:
      iの根の重み

    • diff

      public final long diff(int x, int y)
      二頂点の根の重みの差を返す
      パラメータ:
      x -
      y -
      戻り値:
      重みの差

    • unite

      public final int unite(int x, int y, long w)
      xとyをマージする
      パラメータ:
      x -
      y -
      w -
      戻り値:
      未マージなら1, マージ済で重みが0なら0, 重みがあれば-1

    • 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 final 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