自分の友達 安倍 さん、その 安倍 さんの友達 オバマ さんと、 安倍 さんを介して自分とつながっているとするならば、 つながりを一旦調べると、以後、 安倍 さんを介してつながりの確認をする必要がない。 そんなことが出来てしまうのが Disjoint-set だ。

Disjiont-set を使って Connected component が解けたり、Minimum spanning tree の Kruskal’s algorithm なんかで使われる。

Reference sites