問題タブ [connected-components]

MATLAB で関数を使用する場合regionprops、各接続コンポーネントのバイナリ イメージを抽出するオプションがあります。バイナリ イメージのサイズは、連結要素のサイズに縮小されます。バイナリ イメージのサイズを小さくしたくありません。バイナリ イメージのサイズを元のサイズのままにし、選択した連結成分のみを元のイメージ サイズの対応する位置に表示したい。元の画像サイズで連結成分を抽出するにはどうすればよいですか?

Quick-Findアルゴリズムを使用して、有向グラフ内のすべての弱結合コンポーネントを検索するソリューションを改善しようとしています。

問題文

のリストが与えられた場合、DirectedGraphNodeすべての島 (弱連結成分) を見つけます。

したがって、次の有向グラフが与えられます。

出力は次のようになります (順序は関係ありません)。

Quick-Findアルゴリズムを使用してこれを解決しました。以下のコード:

ただし、このアルゴリズムは最悪の場合、O(N^3)で実行されます。これは、ユニオンの線形検索を毎回行う必要があるためです。これを改善する方法があれば非常に興味があります。

提案ありがとう！

0 と 1 を含むマトリックスが提供されます。すべての 0 は水で、1 は土地です。接続された 1 のグループが島を形成します。1 つの変更で 1 つの 0 を 1 に変換できる場合は、行列に島が 1 つだけになるようにするために必要な変更の最小数を見つけます。

例えば：

マトリックス->

単一の島に変換する変更の最小数は 1 です。(2,2) を 1 に変換します。

インタビューでこんな質問をされました。dfs を使用して島の数を調べました。しかし、さらに解決するためのアプローチを取得できません。

グラフ重心は、等距離またはそれ以下の距離 (N/2) にある頂点です。ここで、N はこの頂点を介して接続された接続コンポーネントのサイズです?! 【要修正?!】

各頂点が重心であるかどうかを確認するように求める CodeForces の問題がありますが、一度に 1 つのエッジを正確に削除および置換した後です。

問題文

この PseudoCode / Algorithm を改良するために助けが必要です。

問題は、このアルゴリズムが少なくとも O(N*M^2)) で実行されることです。受け入れられません。

答えを調べましたが、他の人が使用しているアルゴリズムの高レベルの抽象化を思い付くことができませんでした。これらのソリューションがどのように機能するかを理解するのを手伝ってもらえますか?

ソリューションのリンク

(*1) DFSループ

私はconnectedComponents()pyspark のグラフフレームから使用して、約 1800K の頂点と 500k のエッジを持つかなり大きなグラフの接続コンポーネントを計算しようとしていました。

6時間経っても課題は終わらない。Windowsを搭載した単一のマシンでpysparkを実行しています

を。与えられた設定でそのような計算を行うことは実行可能ですか?

b. 次のような警告メッセージが表示されました

これは何を意味するのでしょうか？

c. グラフフレームでグラフが無向であることをどのように指定できますか? 両方向にエッジを追加する必要がありますか?

1から2、2から3、3から4、.......、n-1からnまでのエッジがあるnノードで構成されるグラフ。

現在、 1からnの順列で構成される配列があり、配列セグメントに基づいて指定されたクエリの数があります。指定されたセグメントのノード (配列要素によって示される) によって形成される連結コンポーネントの数を決定します。たとえば、

配列: 4 5 3 2 1 クエリ: [1, 5]、[1, 4]、[2, 4]

[1, 5]の場合、配列要素は1 2 3 4 5であり、すべてが接続されて単一の接続コンポーネントを形成します。

[1, 4]の場合、配列要素は2 3 4 5であり、単一の連結要素も形成します。

[2, 4]の場合、配列要素は2 3 5であるため、2と3は単一のコンポーネントを形成し、 5は単一のコンポーネントを形成するため、合計2 つの接続されたコンポーネントが[2, 4] にあります。