0

からの値を持つ2つの互いに素な (サイズが のn) セット ( と と呼ばれる)0が与えられた場合、特定のトラバーサルによって形成された最後のエッジ (頂点のペア) を見つける必要があります。112n

トラバーサル アルゴリズム:

  • start from value 1(この値がどのセットにあるかは関係ありません)
  • それを反対側のセットからの最初の自由な値に接続します (最初は実際の値に対して相対的なので、現在の値が と等しい場合は、、、、...、、、3をチェックします)45672n - 12n12
  • 2番目のステップを繰り返す

例：

n = 5
Set "0": { 1, 2, 4, 8, 9 }
Set "1": { 3, 5, 6, 7, 10 }

Traversal path:
1 -> 3 -> 4 -> 5 -> 8 -> 10 -> 2 -> 6 -> 9 -> 7

Answer -> 9 and 7

この問題を2 * (1 + 2 ... + n) = 0(n^2)複雑に解決することができました。しかし、私はより良い解決策があると信じています。

4

1 に答える 1