โปรแกรมเพื่อเพิ่มจำนวนคู่ที่เทียบเท่าให้สูงสุดหลังจากสลับใน Python

สมมติว่าเรามีรายการตัวเลข A และรายการหมายเลข B ที่มีความยาวเท่ากัน นอกจากนี้เรายังมีรายการตัวเลข C แบบ 2 มิติ ซึ่งแต่ละองค์ประกอบอยู่ในรูปแบบ [i, j] ซึ่งบ่งชี้ว่าเราสามารถสลับ A[i] และ A[j] ได้หลายครั้งตามที่เราต้องการ เราต้องหาจำนวนคู่สูงสุดที่ A[i] =B[i] หลังจากการสลับกัน

ดังนั้น หากอินพุตเป็น A =[5, 6, 7, 8], B =[6, 5, 8, 7], C =[[0, 1],[2, 3]] แล้วผลลัพธ์ที่ได้ จะเป็น 4 เนื่องจากเราสามารถสลับ A[0] กับ A[1] จากนั้น A[2] กับ A[3]

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• N :=ขนาด A
• กราฟ :=กราฟโดยติดขอบที่กำหนดแบบสองทิศทาง
• ตอบ :=0
• เห็น :=รายการขนาด N และเติมเท็จ
• สำหรับคุณในช่วง 0 ถึง N ให้ทำ
  • ถ้าเห็น[u] เป็นศูนย์ แล้ว
    • queue :=คิวและแทรก u
    • เห็น[u] :=จริง
    • สำหรับแต่ละโหนดในคิว ทำ
      • สำหรับแต่ละ nei ในกราฟ[โหนด] ทำ
        • ถ้าเห็น[nei] เป็นเท็จ แล้ว
          • ใส่ nei ท้ายคิว
          • เห็น[nei] :=จริง
    • count :=แผนที่ที่มีการนับองค์ประกอบ B[i] สำหรับ i ทั้งหมดที่อยู่ในคิว
    • สำหรับ i แต่ละตัวที่อยู่ในคิว ทำ
      • ถ้า count[A[i]] ไม่ใช่ศูนย์ แล้ว
        • นับ[A[i]] :=นับ[A[i]] - 1
        • อัน :=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