等価クラスのデータ構造

Question

$ e $ は、set $ s $ を介して定義された等価関係になります。 $ e $ へのアクセスは、 $ m（s_1、s_2）= 1 $ $ S_1 $ と $ 0 $ それ以外の場合は。コンピューティング $ m $ は高価です（ $ O（n ^ 2）$ x ）。

私は効率的なデータ構造 $ d $ を探しています " $ s $ < / SPAN>、 $ d $ には、 $ s '$ が $ S $ "？
ナイーブアプローチは、 $ d $ 内の要素によって要素を検索することですが、他の解決策はありますか？

Answer 1

あなたができる最善のことは、共用体探索データ構造を使用して現在知られているすべての同等のものを追跡することです。最初は、各要素は独自のグループです。あなたが2つの要素が同等であることがわかるときはいつでも、あなたはそれらのグループをマージする（union operationを介して）。

その後、リストに答えるためにできる最善のものは、すべてのグループを列挙することです（ $ s $ を含むもの以外）、そのようなグループごとに $ x $ 、 $ s $ が $ x $ 。