通常、union find を使用するときは、1 次元配列を作成し、各インデックスの値を配列内の位置で初期化します。したがって、5 要素の配列の場合、各要素はインデックス ( ) と同じ値になります0-4。
複数の次元を持つユニオン検索データ構造を使用すると、さらに難しくなります。10x10 サイトのグリッドがあるとします。各サイトは最初はオフになっています (多次元配列、各インデックスは value です-1)。私の実装では、配列の次元を指定してサイトを有効にする方法を提供しています。open(4, 3)4 行目に移動し、グリッドの 3 番目のサイトをオンにします。このサイトをオンにした場合、インデックスにどのような値をどのように与えるでしょうか?
最初のサイトとの相対的な位置に独自の価値を与えることを考えていました。そのため、position のサイトに(4, 3)は値 43 が与えられます (下に 10 サイトの 4 行 + 右に 3 つのサイト)。ただし、これには、各サイトを調べて各要素を数えて、格納される値を取得する必要がありますO(n)。4andを文字列に変換し3て結合することもできますが、これは講義の演習であり、彼らが望んでいることではないと思います。
さらに、グリッド上の 2 つのサイトを接続すると、同じ問題が発生します。インデックスを見つけるためにほとんどの配列を調べずに、接続を表す値を決定するにはどうすればよいですか?
私が試みていることを行うためのより良い方法はありますか?