問題タブ [union-find]

私のコードはユニオン検索アルゴリズムを実装しようとしており、id[] 配列と sz[] 配列があります。それらを Union-Find コンストラクターで初期化しますが、それらの配列を Union-Find クラス内のメソッドで使用しようとすると、すべての配列値が 1 に変更されます。理由がわかりません。私が行方不明であることは明らかですか??

Hファイル

CPP ファイル

現在Eclipseで問題に取り組んでいます。データ構造 weightedQuickUnionFind

私が持っているもの：

- ユーザーの ID を含む別の .txt ファイル内のデータのリスト。例：

0 5

0 2

1 3

1 2

2 5

3 7

これが基本的に言っていることは、ID 0 のユーザーが ID 5 のユーザーなどとソーシャル ネットワークで接続されているということです。0 が 2 に接続され、1 が 2 に接続されている場合、0 は 2 に接続されています。とにかく、このリストを使用して、Main クラスと WeightedUnionFind クラスを作成しました。私のメインクラスでは、質問に答えるのに役立ついくつかのメソッドを公開しました。

1. 各個体に何人が接続しているか (つまり、0 に接続しているのは何人か)、何人が接続していないか?
2. ID のグループはいくつ接続されており、最大のグループは何ですか?

これを次から次へと質問であふれさせたくないので、出発点を探しているだけです。

私が言ったように、私はこれまでメソッドをシェルアウトしただけで、これらのメソッドを .txt ファイルに実装するための出発点が必要なだけです。

と呼ばれる別のクラスを作成しました

これが明確だったことを願っています。

次の問題を解決するための古典的なアルゴリズムはありますか。存在量指定子を使用しない和集合検索アルゴリズムに次の入力があるとします。

次に、u.root(x)==u.root(y) をチェックして、x と y が同じサブグラフにあるかどうかを判断できるように、データ構造 u を構築します。

入力は、次の文法によって特徴付けることができます。

ここで、存在量指定子も許可するとします。

そのような入力を処理できるユニオン検索アルゴリズムはどれですか。x と y が同じサブグラフにあるかどうかを u.root(x)==u.root(y) 経由でチェックできるアルゴリズムが何らかのデータ構造 u を構築するとまだ仮定しています。

さらに、u.root(x) は、バインドされた変数で使用すると例外をスローする必要があります。これらの変数はすべて削除され、データ構造の一部ではなくなりました。結果の有効性を変更することなく、サブグラフがそれに応じて削減されるべきであることを意味します。

さよなら

一番下のTLDR

学校でパーコレーション モデルを構築するプログラミング プロジェクトを割り当てられましたが、かなり混乱する問題に遭遇しました。まず、パーコレーション シミュレーションを実行するための API を構築することになっていました。

現在、本は親切にもquickfindUFとWeightedQuickUnionUFを提供しています。私が話したすべてのクラスメートは、作成するように指示された PercolationStats クラスでタイミングを合わせたときに期待される結果を得ましたが、私の結果は非常に大きくなりました。クラスはこちら

これを QuickFindUF で実行すると、percStats(200,100) で約 7 秒かかり、同じ 200,100 で WeightedQuickUnionUF で実行すると、約 50 秒以上かかりますか?? 私は、重み付けされたクイック ユニオンの方が高速であると確信していました。これは、恐ろしい最悪のケースの乱数ジェネレーターで不運になるだけの問題ではありません。何度も実行しましたが、結果はほぼ同じでした。ここでコードをかなり長い間見つめていましたが、なぜ私のコードが間違っているのかわかりません..

TLDR

正しい結果、間違ったタイミング。遅いAPIは何らかの理由で高速であり、その理由がわかりません。QuickFindUF は WeightedQuickUnionUF より高速です。(約 7-8 倍高速)。私は何を間違っていますか？

私は初めてグラフを実装しています。そのために、SPOJ からこの問題を取り上げました。

geeksforgeeks の助けを借りて、ユニオン検索アルゴリズムを適用して、グラフにサイクルが含まれているかどうかを調べましたが、実行時エラー (SIGSEGV) が発生しました。

なぜそうなのか教えてください。