ALGORITHM NOTE Disjoint Sets, Union Find

Disjoint Sets に対して、「指定された２つの要素 x, y が、同じ集合に属するか？」どうかを調べる操作、つまり findSet(x) == findSet(y) は Union Find と呼ばれます。 Disjoint Sets の表現 Disjoint Sets を実装する方法はいくつかありますが、ここでは Disjoint Sets forests と呼ばれる"森"の構造を用います。森を構成する tree (木)が各集合を表し、tree の各ノードが集合内の各要素を表します。 findSet( x ) 集合を区別するために、各 tree の根を代表 (representative) とし、集合を識別するために用います。従って、findSet( x ) は、要素 x が属する tree （集合）の根を値として返します。これを実現するために、各ノードはそれ自身から代表まで到

[androidzaurus]

union-find

[morita_non]

UnionSet