feat: Maximize the Number of Equivalent Pairs After Swaps]

robot · robot · commit e65052f2e20a · 2021-12-23T21:21:44.000+08:00
diff --git a/README.md b/README.md
@@ -252,6 +252,7 @@ leetcode 题解，记录自己的 leetcode 解题之路。
 - [Minimum Dropping Path Sum](./problems/Minimum-Dropping-Path-Sum.md)
 - [Longest-Matrix-Path-Length](./problems/Longest-Matrix-Path-Length.md)
 - [Every Sublist Min Sum](./problems/Every-Sublist-Min-Sum.md)
+- [Maximize the Number of Equivalent Pairs After Swaps](./problems/Maximize-the-Number-of-Equivalent-Pairs-After-Swaps.md)
 
 - [0002. 两数相加](./problems/2.add-two-numbers.md)
 - [0003. 无重复字符的最长子串](./problems/3.longest-substring-without-repeating-characters.md)
diff --git a/SUMMARY.md b/SUMMARY.md
@@ -105,6 +105,7 @@
   - [Bus Fare](./problems/Bus-Fare.md) 👍
   - [Minimum Dropping Path Sum](./problems/Minimum-Dropping-Path-Sum.md)
   - [Every Sublist Min Sum](./problems/Every-Sublist-Min-Sum.md)
+  - [Maximize the Number of Equivalent Pairs After Swaps](./problems/Maximize-the-Number-of-Equivalent-Pairs-After-Swaps.md)
   - [0002. 两数相加](./problems/2.add-two-numbers.md)
   - [0003. 无重复字符的最长子串](./problems/3.longest-substring-without-repeating-characters.md)
   - [0005. 最长回文子串](./problems/5.longest-palindromic-substring.md)
diff --git a/problems/Maximize-the-Number-of-Equivalent-Pairs-After-Swaps.md b/problems/Maximize-the-Number-of-Equivalent-Pairs-After-Swaps.md
@@ -0,0 +1,119 @@
+## 题目地址（690. Maximize the Number of Equivalent Pairs After Swaps）
+
+https://binarysearch.com/problems/Maximize-the-Number-of-Equivalent-Pairs-After-Swaps
+
+## 题目描述
+
+```
+You are given a list of integers of the same length A and B. You are also given a two-dimensional list of integers C where each element is of the form [i, j] which means that you can swap A[i] and A[j] as many times as you want.
+
+Return the maximum number of pairs where A[i] = B[i] after the swapping.
+
+Constraints
+
+n ≤ 100,000 where n is the length of A and B
+m ≤ 100,000 where m is the length of C
+Example 1
+Input
+A = [1, 2, 3, 4]
+B = [2, 1, 4, 3]
+C = [
+    [0, 1],
+    [2, 3]
+]
+Output
+4
+Explanation
+We can swap A[0] with A[1] then A[2] with A[3].
+```
+
+## 前置知识
+
+- 并查集
+- BFS
+- DFS
+
+## 并查集
+
+### 思路
+
+这道题的核心在于如果 A 中的 [0,1] 可以互换，并且 [1,2] 可以互换，那么 [0,1,2] 可以任意互换。
+
+也就是说互换**具有联通性**。这种联通性对做题有帮助么？有的！
+
+根据 C 的互换关系，我们可以将 A 分为若干联通域。对于每一个联通域我们可以任意互换。因此我们可以枚举每一个联通域，对联通域中的每一个索引 i ，我们看一下 B 中是否有对应 B[j] == A[i] 其中 i 和 j 为同一个联通域的两个点。
+
+具体算法：
+
+- 首先根据 C 构建并查集。
+- 然后根据将每一个联通域存到一个字典 group 中，其中 group[i] = list，i 为联通域的元，list 为联通域的点集合列表。
+- 枚举每一个联通域，对联通域中的每一个索引 i ，我们看一下 B 中是否有对应 B[j] == A[i] 其中 i 和 j 为同一个联通域的两个点。累加答案即可
+
+### 代码
+
+代码支持：Python3
+
+Python3 Code:
+
+```py
+
+class UF:
+  def __init__(self, M):
+      self.parent = {}
+      self.cnt = 0
+      # 初始化 parent，size 和 cnt
+      for i in range(M):
+          self.parent[i] = i
+          self.cnt += 1
+
+  def find(self, x):
+      if x != self.parent[x]:
+          self.parent[x] = self.find(self.parent[x])
+          return self.parent[x]
+      return x
+  def union(self, p, q):
+      if self.connected(p, q): return
+      leader_p = self.find(p)
+      leader_q = self.find(q)
+      self.parent[leader_p] = leader_q
+      self.cnt -= 1
+  def connected(self, p, q):
+      return self.find(p) == self.find(q)
+
+class Solution:
+    def solve(self, A, B, C):
+        n = len(A)
+        uf = UF(n)
+        for fr, to in C:
+            print(fr, to)
+            uf.union(fr, to)
+        group = collections.defaultdict(list)
+
+        for i in uf.parent:
+            group[uf.find(i)].append(i)
+        ans = 0
+        for i in group:
+            indices = group[i]
+            values = collections.Counter([A[i] for i in indices])
+            for i in indices:
+                if values[B[i]] > 0:
+                    values[B[i]] -= 1
+                    ans += 1
+        return ans
+
+```
+
+**复杂度分析**
+
+令 n 为数组 A 的长度，v 为图的点数，e 为图的边数。
+
+- 时间复杂度：$O(n+v+e)$
+- 空间复杂度：$O(n)$
+
+## 总结
+
+我们也可以使用 BFS 或者 DFS 来生成 group，生成 group 后的逻辑大家都是一样的，这两种解法留给大家来实现吧。
+
+力扣的小伙伴可以[关注我](https://leetcode-cn.com/u/fe-lucifer/)，这样就会第一时间收到我的动态啦~
+
+以上就是本文的全部内容了。大家对此有何看法，欢迎给我留言，我有时间都会一一查看回答。更多算法套路可以访问我的 LeetCode 题解仓库：https://github.com/azl397985856/leetcode 。 目前已经 46K star 啦。大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。
