Problem statement

https://binarysearch.com/problems/Maximize-the-Number-of-Equivalent-Pairs-After-Swaps/

Solution

First, we create connected components. Then for each connected component we create counter for elements of A and B. Then we find intersection of these counters to calculate how many elements we can keep in place.

Complexity

It is O(n log n) for time and O(n) for space.

Code

class DSU:
    def __init__(self, N):
        self.p = list(range(N))

    def find(self, x):
        if self.p[x] != x:
            self.p[x] = self.find(self.p[x])
        return self.p[x]

    def union(self, x, y):
        xr = self.find(x)
        yr = self.find(y)
        self.p[xr] = yr

class Solution:
    def solve(self, A, B, C):
        n = len(A)
        dsu = DSU(n)
        for x, y in C:
            dsu.union(x, y)
        d1, d2 = defaultdict(list), defaultdict(list)
        for i in range(n):
            d1[dsu.find(i)] += [A[i]]
            d2[dsu.find(i)] += [B[i]]

        ans = 0
        for x in d1:
            ans += sum((Counter(d1[x]) & Counter(d2[x])).values())

        return ans