また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=2524
Disjoint Setsの個数を求める問題．指定された二つの要素を含む集合を連結していく．
解答
互いに素な集合を表現するためのclass「DisjointSet」を用意し，それらを操作するためのメンバ関数を定義した．unite_set()の最初から"if (x != y)"までの部分がUnion Findの操作にあたる．集合の個数についてはあらかじめ変数countを用意しておき，uniteする度にその値をデクリメントしていくようにした．
なお，問題に"Huge input, scanf is recommended."と書かれていたため，今回はcin/coutの代わりにscanf/printfを使っている．
ソースは以下の通り．
