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의 크기
graph :=주어진 모서리를 양방향으로 연결하여 그래프.
ans :=0
seen :=크기가 N이고 False로 채워진 목록
0에서 N까지의 범위에 있는 u에 대해
- 본[u]이 0이면
  - queue :=대기열 및 삽입 u
  - 본[u] :=사실
  - 대기열의 각 노드에 대해 다음을 수행합니다.
    - 그래프[노드]의 각 nei에 대해 다음을 수행합니다.
      - see[nei]가 거짓이면
        
        대기열 끝에 nei 삽입
        
        본[nei] :=사실입니다
  - count :=대기열에 있는 모든 i에 대한 B[i] 요소 수를 포함하는 맵
  - 대기열에 있는 각 i에 대해 다음을 수행합니다.
    - count[A[i]]가 0이 아니면
      - 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]]