Pythonでのみ、指定されたインデックス間のスワップを使用して配列を並べ替えることができるかどうかを確認します

範囲[0、n –1]の一意の値を持つnumsという配列があるとします。この配列はソートされていません。また、ペアの別の配列があり、各ペアには、配列の要素を交換できるインデックスが含まれています。複数回交換できます。これらのスワップを使用して、配列をソートされた順序で配置できるかどうかを確認する必要があります。

したがって、入力がnums =[6,1,7,3,0,5,4,2]ペア=[（0,4）、（6,0）、（2,7）]のようである場合、インデックス（2,7）をスワップできるため、出力はTrueになります。配列は[6,1,2,3,0,5,4,7]になり、次にスワップ（6,0）になり、配列は[4、 1,2,3,0,5,6,7]、次に（0,4）をスワップして[0,1,2,3,4,5,6,7]を取得します。

これを解決するには、次の手順に従います-

• N：=numのサイズ、P：=ペア配列のペアの数
• v：=N個のサブリストを持つリスト
• 訪問：=新しいセット
• 0からPの範囲のiについては、
  • ペアの2番目のインデックス[i]をv[ペアの最初のインデックス[i]]に挿入します
  • ペアの最初のインデックス[i]をv[ペアの2番目のインデックス[i]]に挿入します
• 0からNの範囲のiについては、
  • 私が訪問されていない場合は、
    • que：=両端キュー
    • arr_first：=新しいリスト
    • arr_second：=新しいリスト
    • 私を訪問済みとしてマーク
    • queの最後にiを挿入
    • queが空でない間は、
      • u：=queのfront要素とqueのfront要素を削除します
      • arr_firstの最後にuを挿入
      • arr_secondの最後にnums[u]を挿入します
      • v [u]の各sについて、実行します
        • sにアクセスしない場合は、
          • 訪問済みとしてマーク
          • キューの最後にsを挿入
    • arr_first：=リストを並べ替えるarr_first
    • arr_second：=リストを並べ替えるarr_second
    • arr_firstがarr_secondと同じでない場合、
      • Falseを返す
• Trueを返す

理解を深めるために、次の実装を見てみましょう-

サンプルコード

from collections import deque

def solve(nums, pairs):
   N = len(nums)
   P = len(pairs)
   v = [[] for i in range(N)]
   visited = set()
 
   for i in range(P):
      v[pairs[i][0]].append(pairs[i][1])
      v[pairs[i][1]].append(pairs[i][0])
 
   for i in range(N):
      if i not in visited:
         que = deque()
         arr_first = []
         arr_second = []
 
         visited.add(i)
         que.append(i)
 
         while len(que) > 0:
           u = que.popleft()
           arr_first.append(u)
           arr_second.append(nums[u])
 
           for s in v[u]:
               if s not in visited:
                 visited.add(s)
                 que.append(s)
 
         arr_first = sorted(arr_first)
         arr_second = sorted(arr_second)
         
         if arr_first != arr_second:
           return False
   return True
 
nums = [6,1,7,3,0,5,4,2]
pairs = [(0,4),(6,0),(2,7)]
print(solve(nums, pairs))

入力

[6,1,7,3,0,5,4,2], [(0,4),(6,0),(2,7)]

出力

True