問題タブ [union-find]

私はこの課題を解決しています: https://open.kattis.com/problems/virtualfriends

私のソリューションは機能しているようですが、kattis のテスト ケースの実行が遅すぎるため、コードの効率を改善するにはどうすればよいか考えていました。これを行うためにカスタムメイドの共用体検索構造を使用し、「友達」をツリーマップに格納して参照しています。

これは、 Narasimha Karumanchi (disjoint set ADT)によるデータ構造の本からの段落です。

高速検索実装（クイック検索）

このメソッドは配列を使用します。配列には各要素のセット名が含まれています。

この表現では、union(a,b) [a, がセット i にあり、b がセット j にあると仮定して] を実行するには、配列全体をスキャンして、すべての i を j に変更する必要があります。これはO（n）を取ります。

私の質問 1

検索操作に O(1) がかかる場合、完全な配列をスキャンしてすべての i を j に変更する理由

============

(ブック 8.8 セクション)

私の2.質問

親を使用してどのように問題を解決しますか? そして、ルートと親のアプローチの両方が、どのようにしてスキュー ツリーを提供するのでしょうか?

Union Findを勉強しています。

これらのユニオン操作を組み合わせてこのグラフを作成する方法は理解していますが、ID 変数がどのように割り当てられているかはわかりません。最初は、各グラフのサイズだと思っていましたが、最初のグラフのサイズが 5 で、2 番目のグラフのサイズが 3 であるため、そうではありません。