Union Find木

互いに素な集合 Union Find| データ構造ライブラリ | Aizu Online Judge

B: Union Find - AtCoder Typical Contest 001 | AtCoder

 

 蟻本を読んでてわからなかったので、いろいろググったら、やっと簡易版がわかるようになった。

 

蟻本のpar[x] = Xの所は何を示しているのかというと、par[x]のxは要素そのものであるのに対して、Xは所属グループ・・・つまりノードの親を示している。

 

簡単な例を書くと、初期化したものは以下のようになる。

par[0] = 0, par[1] = 1, par[2] = 2

rank[0] = 0, rank[1] = 0, rank[2] = 0

 

初期値の場合、すべてが根になる par[x] == xが根の条件になるので。

 

ここから、x =0, y=1として結合させると、x = root(0) = 0, y = root(1) = 1となり、par[y=1] = (x=0)となるため、 par[1] = 0となり、要素1は要素0を根とするグループに所属することになる。イメージ:(0) → (1)

 

root(1)を求めると、root(1) = 0となるため、次のステップでroot(0) = 0となり、1の根が0であることを示している。

 

x=1, y=2でもう一回結合すると、par[2] = 0となるので、要素2も要素0に所属することになり、ノードは (1) ← (0) → (2) となる。

 

・・・なるほどね、よくできている。これを考えた人はすごいな。

 

とりあえず簡易版は理解できたので、次は下のリンク先のものを勉強するとします。

 

Union-Find木の参考になるサイトと例題 - ゆらのふなびと

Union-Find木(3題) - 藤 遥のブログ

 

 

Remove all ads