グラフ検索と接続操作のための単一の配列を使用してログ時間の複雑さを得ることができますか？

Question

グラフ検索（AとBが接続されているかどうか）を実行し、単一の配列を使用してログ時に接続（接続AとBを接続）できますか？

私のようないくつかのアルゴを学んだ：

は迅速（ルックアップで接続して、一定時間内に線形時間）を見つける - （一定の時間がに接続して、平均N/2つのアレイ

迅速組合をルックアップ） - 単一配列

加重和（ルックアップと定数接続時間でのログ時間）しかし、このアルゴリズムでは2つの配列、1つはノード、もう1つは各ノードに接続されたノードの数が必要ですオード。

私は好奇心を求めています。単一の配列を使用して、加重和集合の複雑さを得ることは可能ですか？

Answer 1

Disjoint-Setを使用できます。これはフォレストとして機能しますが、ノードごとにrootフィールドの代わりに配列を使用して、常にrootsの配列を使用してこのフォレストを実装できます。

この実装のarmotized複雑さがサブ対数あり、そして多くの場合、あなたが望むものO(log*(n))

Answer 2

として標識されるDisjoint-Setです。あなたは非常に簡単な説明を見つけることができますhere