千问 LeetCode 2076.处理含限制条件的好友请求 public boolean[] friendRequests(int n, int[][] restrictions,

这是一道经典的并查集（Union-Find）应用题。

🧠 核心思路解析

1. 问题本质：

   • 我们需要维护一组动态变化的“朋友圈”（连通分量）。
   • 每当有一个好友请求时，我们需要判断：如果同意这个请求，会不会导致某些被禁止的人（restrictions）变成朋友（直接或间接）？
   • 如果不会违反限制，就同意请求（合并集合）；如果会违反，就拒绝请求（保持原状）。

2. 并查集的作用：

   • 并查集非常适合处理这种“动态连通性”问题。它可以高效地判断两个元素是否在同一个集合中，以及合并两个集合。

3. 处理流程：

   • 初始化并查集，每个人最初都是独立的。
   • 遍历每一个好友请求 (u, v)：
     1. 找到 u 和 v 的根节点 rootU 和 rootV。
     2. 如果 rootU == rootV，说明他们已经是朋友了，直接返回 true。
     3. 如果 rootU != rootV，我们需要预判：假设合并这两个集合，会不会触犯 restrictions？
        • 遍历所有的限制条件 (x, y)。
        • 找到 x 和 y 的根节点 rootX 和 rootY。
        • 冲突检测：如果合并 u 和 v 后，导致 x 和 y 连通了，那就是冲突。
        • 具体来说，如果 (rootU == rootX 且 rootV == rootY) 或者 (rootU == rootY 且 rootV == rootX)，说明合并后 x 和 y 就在同一个集合里了，这是不允许的。
     4. 如果没有冲突，执行合并操作，返回 true；否则返回 false。

4. 关键细节：

   • 在检查冲突时，我们使用的是当前的并查集状态。
   • 只有在确定没有冲突后，才真正执行 union 操作。

💻 Java 代码实现

class Solution {
// 并查集父节点数组
private int[] parent;

public boolean[] friendRequests(int n, int[][] restrictions, int[][] requests) { // 1. 初始化并查集 parent = new int[n]; for (int i = 0; i < n; i++) { parent[i] = i; // 每个人最初指向自己 } boolean[] result = new boolean[requests.length]; // 2. 处理每一个好友请求 for (int i = 0; i < requests.length; i++) { int u = requests[i][0]; int v = requests[i][1]; int rootU = find(u); int rootV = find(v); // 如果已经在同一个集合，直接成功 if (rootU == rootV) { result[i] = true; continue; } // 3. 预判：如果合并 rootU 和 rootV，是否会违反 restrictions？ boolean canConnect = true; for (int[] restriction : restrictions) { int x = restriction[0]; int y = restriction[1]; int rootX = find(x); int rootY = find(y); // 检查合并后是否会导致 x 和 y 连通 // 情况1: u所在的集合包含x, v所在的集合包含y // 情况2: u所在的集合包含y, v所在的集合包含x if ((rootU == rootX && rootV == rootY) || (rootU == rootY && rootV == rootX)) { canConnect = false; break; } } // 4. 根据预判结果决定是否合并 if (canConnect) { union(u, v); // 合并集合 result[i] = true; } else { result[i] = false; } } return result; } // 查找根节点（带路径压缩） private int find(int x) { if (parent[x] != x) { parent[x] = find(parent[x]); } return parent[x]; } // 合并两个集合 private void union(int x, int y) { int rootX = find(x); int rootY = find(y); if (rootX != rootY) { parent[rootX] = rootY; } }

}

📝 复杂度分析

1. 时间复杂度：O(M times K times alpha(N))

   • M 是 requests 的长度。
   • K 是 restrictions 的长度。
   • alpha(N) 是并查集查找操作的平均时间复杂度（阿克曼函数的反函数，非常小，接近常数）。
   • 对于每个请求，我们最坏情况下需要遍历所有 restrictions 来检查冲突。

2. 空间复杂度：O(N)

   • 主要用于存储并查集的 parent 数组。

💡 示例 walkthrough

以示例 1 为例：

• n = 3, restrictions = [[0,1]], requests = [[0,2],[2,1]]

1. 初始状态：parent = [0, 1, 2]
2. 处理请求 [0, 2]：
   • find(0) = 0, find(2) = 2。不同集合。
   • 检查限制 [0, 1]：find(0) = 0, find(1) = 1。
   • 合并 0 和 2 后，0 的集合（含0）和 2 的集合（含2）合并。
   • 检查冲突：(00 && 21) 或 (01 && 20) 都不成立。
   • 无冲突，执行 union(0, 2)。parent = [0, 1, 0]。结果 true。
3. 处理请求 [2, 1]：
   • find(2) = find(0) = 0, find(1) = 1。不同集合。
   • 检查限制 [0, 1]：find(0) = 0, find(1) = 1。
   • 合并 2（根0）和 1（根1）后，集合0和集合1会合并。
   • 检查冲突：(00 && 11) 成立！这意味着合并后 0 和 1 会连通。
   • 有冲突，不执行合并。结果 false。

最终结果：[true, false]。