DSU

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

public interface DSU

UnionFindのベースとなるインターフェース Disjoint Set Union

メソッドの概要

修飾子とタイプ

メソッド

説明

ArrayList<ArrayList<Integer>>

groups()

グラフを連結成分に分け、その情報を返す

int

root(int i)

頂点iの根を返す

default boolean

same(int i, int j)

二頂点が同じ連結成分に所属しているかを返す

int

size()

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
  
  ArrayList<ArrayList<Integer>> groups()
  
  グラフを連結成分に分け、その情報を返す
  戻り値:
  
  グラフを連結成分に分けた時の状態
  
  関連項目:
  
  atcoder::dsu::groups