Disjoint SetsにおけるUnion Find - ぬいぐるみライフ？

またPKUの問題を解いてみた．今回のテーマはUnion Find． Union Find Disjoint Sets(互いに素な集合)におけるUnion Findとは，指定された二つの要素x，yが同じ集合に含まれるかどうかを調べるアルゴリズムのこと．集合と要素を多分木とその葉で表現し，木の根を集合の代表要素とみなすことによって，二つの要素が同じ集合に含まれるかどうかの判定は代表要素の比較操作に落とすことができる．単純な木を用いた場合は代表要素の検索には最悪O(N)の計算量がかかってしまうが，この木に適当な平衡操作を行うことによって，計算量をO(A(N))に抑えられることが知られている(A(N)はアッカーマン関数の逆関数)． 問題 Problem 2524 - Ubiquitous Religions http://acm.pku.edu.cn/JudgeOnline/problem?id=