各コンポーネントがコンポーネント全体で共通の行または列を持つように、疎行列を最小数の接続コンポーネントに分割するにはどうすればよいですか。このタスクを最小限の時間で実行するには、どのデータ構造を使用する必要がありますか。そのためには、各コンポーネントの要素数を最大化する必要があると考えたため、入力を取得しながら、各行と列に要素数を保存しました。リストを並べ替えてから、行または列を max(min(行内の要素、列内の要素))、つまり、
row 5-1 column 4-2
row 4-1 column 3-2
row 3-2 column 2-3
row 2-2 column 1-3
row 1-10
行列の場合:
x
x
x x
x x
xxxxxxxxxx
(x はゼロ以外の位置を表します)(この行列の最終出力は 4 になるはずです)
ここで、左下隅は 1,1 です
次に、最初に列 1 を削除します。次に、残りの配列を更新する必要があります。これには多くの時間がかかり、各行と列のリストを格納することも、多くのメモリを使用するため実行できません。パーティションの最小数を指定するだけで、実際にマトリックスを分割する必要はありません。指定された行列では、パーティションとして (row1,row2,row3,colum2-(1,2)) を使用してパーティション化できます。
編集:または同等に、これを 2 つの数値が関連付けられた要素のセットと考えることができ、各パーティションが 2 つの数値のうちの 1 つを共通として持つように最小数のパーティションを出力します。