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

สมมติว่าเรามีลิสต์ A และ B ความยาวเท่ากัน และลิสต์ 2 มิติ C แต่ละคู่ [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 (สลับ 0↔1 และ 2↔3)

ขั้นตอนการแก้ปัญหา (Graph Components + Greedy Matching)

1. N = len(A)
2. สร้าง graph จาก edges แบบ bidirectional
3. ans = 0, seen = [False] * N
4. สำหรับ u จาก 0 ถึง N-1:
   • ถ้า not seen[u]:
     • BFS/DFS หา connected component ทั้งหมด เก็บใน queue
     • นับ count ของ B[i] สำหรับ i ใน queue
     • สำหรับแต่ละ i ใน queue:
       • ถ้า count[A[i]] > 0: count[A[i]] -= 1, ans += 1
5. คืนค่า ans

ตัวอย่างโค้ด Python

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))  # Output: 4

อินพุต / เอาต์พุต

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

Output: 4