問題タブ [union-find]

kruskal アルゴリズムを使用して、spoj でこの MST の質問を解決しようとしています。私のプログラムはすべてのテスト ケースで動作するように見えますが、spoj はこのコードに WA を繰り返し与えています。

このコードで失敗したテスト ケースを見つけることができません。誰かが私が間違っていることを指摘してもらえますか。

これは宿題の質問ではないことに注意してください。私は Kattis のトレーニングを行っており、Union-Find パラダイムの使用を必要とする質問にたどり着きました。問題の性質を考慮して、独自の UnionFind データ構造を実装することにしました。DS のインターフェースが以下をサポートする必要があることを理解しています。

1. メイクセット
2. find(elem) -> そのセットの代表への参照を返します
3. merge(firstElem, secondElem) -> そのセットの 2 つの親をマージします (バランスが取れていることも確認します)

問題は、インデックスが値であり、セットの代表が常にそのインデックスの値である配列を使用して通常実装される整数をサポートするために、このデータ構造を実装していないことです。代わりに、セットに文字列が含まれており、データ構造を選択するのが難しいと感じています。

互いに素な集合に関するアルゴリズムを研究しています。

そして、の章Fast FIND Implementation (Quick Find)

データ構造を以下に示します。

例えば）

(上記の例)では[number] = set name、number はセット名の要素です。

したがって、番号 0 はセット 3 にあり、番号 1 はセット 5 にある、などです。

Union(a, b) を実行するには (a がセット i にあり、b がセット j にあると仮定)、O(n) 操作が必要です。私はこれを知っている。理由を以下に示します（疑似コード）：

しかし、本の中で、私はこれを理解できません：

n - 1 結合のシーケンスは、最悪の場合 O(n^2) 時間かかります。O(n^2) 個の FIND 操作がある場合、各 UNION または FIND 操作の平均時間の複雑さは O(1) であるため、このパフォーマンスは問題ありません。FIND が少ない場合、この複雑さは受け入れられません。

これらの文の意味と、複雑さが O(n^2) である理由がわかりません。上で書いたコードのような複雑さは想像できません。