Spaghetti Source - Union Find

説明 Union Find は互いに素な集合を扱うための道具である．Union Find を用いると以下の操作を高速に行うことができる． union_set(x,y): x が入っている集合と y が入っている集合を併合する． find_set(x,y): x と y が同じ集合に入っているかを判定する． make_set(x): x のみが入る集合 {x} を作る． アルゴリズムは次の考え方による．集合を多分木で管理し，木の根を集合の代表元とみなす．集合の併合は木の併合，二つの要素が同じ集合に入るかどうかは代表元が等しいかどうかの比較で行う． これらの走査を単純な木で行った場合，検索や併合に最悪 O(n) かかってしまう．そこで平衡操作を取る．具体的には木の要素を手繰ったとき，それらの親ポインタをすべて根に張り替える．このときの計算量を見積もるのは複雑だが，ならし解析によって O(A(n

[okagawa]

Union Find構造