問題タブ [disjoint-union]

償却された複雑さまたはユニオン検索、クイック検索操作に関する情報源はたくさんありますが、単一のユニオン操作の複雑さの証拠については何も見つかりませんでした。

では、ユニオン操作の償却された複雑さがO(log n)であることをどのように証明できますか。

ありがとう。

cp-algorithms のWeb サイトから:

DSU の特定のアプリケーションでは、頂点とそのセットの代表との間の距離 (つまり、現在のノードからツリーのルートまでのツリー内のパスの長さ) を維持する必要がある場合があります。

次のコードが実装として提供されます。

この代表者までの距離がどのように役立つかわかりません。これは、データ構造内のセットのリーダーまでの距離を表すだけであり、元の問題とは関係がない可能性があるためです。
union_sets や make_set などの操作を行ったときに距離がどのように変化するかを確認するためにいくつかの例を試しましたが、何もわかりませんでした。私の質問は、この「代表者までの距離」が何を表しているのか、またはその意味や用途は何なのかということです。それを視覚化または理解するための助けをいただければ幸いです。