Chương trình tối đa hóa số cặp tương đương sau khi hoán đổi bằng Python

Cho hai danh sách A và B cùng độ dài, và danh sách cặp C cho phép hoán đổi A[i] và A[j] bất kỳ lần nào. Tối đa hóa số cặp i sao cho A[i] == B[i] sau hoán đổi.

Ví dụ: A = [5,6,7,8], B = [6,5,8,7], C = [[0,1],[2,3]] → 4 (hoán đổi 0↔1 và 2↔3).

Quy trình giải quyết (Connected Components + Greedy)

1. Xây dựng đồ thị từ các cạnh trong C.
2. Tìm các thành phần liên thông (connected components) bằng BFS/DFS.
3. Với mỗi thành phần:
   • Đếm tần suất giá trị trong B tại các chỉ số của thành phần.
   • Với mỗi chỉ số i trong thành phần, nếu A[i] có trong đếm của B, ghép cặp và giảm đếm.
4. Tổng số cặp ghép được là kết quả.

Ví dụ mã nguồn

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

Đầu vào

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

Đầu ra

4