cp-library-kt/lib.dsu/DSU

DSU

class DSU(size: Int)(source)

集合のマージを高速に行うデータ構造

Constructors

constructor(size: Int)

Functions

fun groups(): List<List<Int>>

各集合を返す

fun leader(v: Int): Int

v が属する集合の代表元を返す

fun merge(u: Int, v: Int): Int

u が属する集合と v が属する集合を合併し、新たな集合の代表元を返す

fun same(u: Int, v: Int): Boolean

u と v が同じ集合に属するかを返す

fun sizeOf(v: Int): Int

v が属する集合の大きさを返す