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

这是一道经典的并查集Union-Find应用题。 核心思路解析问题本质我们需要维护一组动态变化的“朋友圈”连通分量。每当有一个好友请求时我们需要判断如果同意这个请求会不会导致某些被禁止的人restrictions变成朋友直接或间接如果不会违反限制就同意请求合并集合如果会违反就拒绝请求保持原状。并查集的作用并查集非常适合处理这种“动态连通性”问题。它可以高效地判断两个元素是否在同一个集合中以及合并两个集合。处理流程初始化并查集每个人最初都是独立的。遍历每一个好友请求 (u, v)找到 u 和 v 的根节点 rootU 和 rootV。如果 rootU rootV说明他们已经是朋友了直接返回 true。如果 rootU ! rootV我们需要预判假设合并这两个集合会不会触犯 restrictions遍历所有的限制条件 (x, y)。找到 x 和 y 的根节点 rootX 和 rootY。冲突检测如果合并 u 和 v 后导致 x 和 y 连通了那就是冲突。具体来说如果 (rootU rootX 且 rootV rootY) 或者 (rootU rootY 且 rootV rootX)说明合并后 x 和 y 就在同一个集合里了这是不允许的。如果没有冲突执行合并操作返回 true否则返回 false。关键细节在检查冲突时我们使用的是当前的并查集状态。只有在确定没有冲突后才真正执行 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; } }} 复杂度分析时间复杂度O(M times K times alpha(N))M 是 requests 的长度。K 是 restrictions 的长度。alpha(N) 是并查集查找操作的平均时间复杂度阿克曼函数的反函数非常小接近常数。对于每个请求我们最坏情况下需要遍历所有 restrictions 来检查冲突。空间复杂度O(N)主要用于存储并查集的 parent 数组。 示例 walkthrough以示例 1 为例n 3, restrictions [[0,1]], requests [[0,2],[2,1]]初始状态parent [0, 1, 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。处理请求 [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]。