接続された頂点のペアに基づいてグラフを構築する

質問内容

「n 行には正の整数のペアが含まれており、各ペアはグラフ内の 2 つの頂点間の接続を識別します。」という場合に、個別のグラフが何個作成されるかを確認する必要があります。 [4 3]、[1 4]、[5 6] の 3 つのペアがあるとします。 [4 3]&[1 4] は 1 つのグラフ [1 3 4] にマージされるため、答えは 2 です。2 番目のグラフは [5 6] です。 別のペアを追加すると: [4 3]、[1 4]、[5 6]、[4 6]、答えは 1 になります (接続されているグラフは 1 つだけです: [1 3 4 5 6])。 p>

Java を使用してこの問題を解決することができましたが、効率的ではなく、10000 ペアを超えると非常に遅くなりました。コードはほぼ次のようになります:

リーリー

パフォーマンスを向上させるにはどうすればよいですか?既製のソリューションを求めているわけではありませんが、処理を大幅に高速化する、私が知らないアルゴリズムがあるかもしれません。

正解

連結成分の数を取得するには、素集合を使用できます。これは、入力がエッジの list であると仮定した単純な実装です。

リーリー

ノードの数 (n) がわかっており、すべてのノード ラベルが 1 から n までの整数であると仮定できる場合、次のように渡すことができます。 map の代わりに配列を使用して最適化し、エッジが追加されるときに接続されたコンポーネントの数を追跡します。

リーリー

以上が接続された頂点のペアに基づいてグラフを構築するの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。