Pythonで交換した後、同等のペアの数を最大化するプログラム

同じ長さの番号Aのリストと番号Bのリストがあるとします。また、各要素が[i、j]の形式である数値Cの2Dリストがあります。これは、A[i]とA[j]を何度でも交換できることを示しています。スワッピング後、A [i] =B[i]となるペアの最大数を見つける必要があります。

したがって、入力がA =[5、6、7、8]、B =[6、5、8、7]、C =[[0、1]、[2、3]]の場合、出力はA[0]をA[1]と交換し、次にA[2]をA[3]と交換できるため、4になります。

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

• N：=Aのサイズ
• グラフ：=指定されたエッジを双方向にアタッチすることによるグラフ。
• ans：=0
• 見た：=サイズNのリストで、Falseで埋める
• 0からNの範囲のuについては、
  • sawed [u]がゼロの場合、
    • queue：=キューと挿入u
    • sawed [u]：=True
    • キュー内のノードごとに、
      を実行します。
      • グラフ[ノード]の各neiについて、実行します
        • sawed [nei]がfalseの場合、
          • キューの最後にneiを挿入
          • sawed [nei]：=True
    • count：=キュー内のすべてのiのB[i]要素の数を含むマップ
    • キュー内の各iについて、
      • count [A [i]]がゼロ以外の場合、
        • count [A [i]]：=count [A [i]]-1
        • ans：=ans + 1
• 回答を返す

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

例

from collections import Counter
class Solution:
   def solve(self, A, B, edges):
      N = len(A)
      graph = [[]
      for _ in range(N)]
         for u, v in edges:
            graph[u].append(v)
            graph[v].append(u)
      ans = 0
      seen = [False] * N
      for u in range(N):
         if not seen[u]:
            queue = [u]
            seen[u] = True
            for node in queue:
               for nei in graph[node]:
                  if not seen[nei]:
                     queue.append(nei)
                     seen[nei] = True
            count = Counter(B[i] for i in queue)
            for i in queue:
               if count[A[i]]:
                  count[A[i]] -= 1
            ans += 1
      return ans
ob = Solution()
A = [5, 6, 7, 8]
B = [6, 5, 8, 7]
C = [[0, 1],[2, 3]]
print(ob.solve(A, B, C))

入力

[5, 6, 7, 8], [6, 5, 8, 7], [[0, 1],[2, 3]]

出力

4