LeetCode 题解工作台
处理含限制条件的好友请求
给你一个整数 n ，表示网络上的用户数目。每个用户按从 0 到 n - 1 进行编号。 给你一个下标从 0 开始的二维整数数组 restrictions ，其中 restrictions[i] = [x i , y i ] 意味着用户 x i 和用户 y i 不能 成为 朋友 ，不管是 直接 还是通…
2
题型
5
代码语言
3
相关题
当前训练重点
困难 · 并查集
答案摘要
我们可以用并查集来维护朋友关系，然后对于每个请求，判断是否满足限制条件。 对于当前请求的两个人 $(u, v)$，如果他们已经是朋友，那么可以直接接受请求；否则，我们遍历限制条件，如果存在限制条件 $(x, y)$，使得 和 互为朋友并且 和 互为朋友，或者 和 互为朋友并且 和 互为朋友，那么就不能接受请求。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 并查集 题型思路
题目描述
给你一个整数 n ，表示网络上的用户数目。每个用户按从 0 到 n - 1 进行编号。
给你一个下标从 0 开始的二维整数数组 restrictions ，其中 restrictions[i] = [xi, yi] 意味着用户 xi 和用户 yi 不能 成为 朋友 ，不管是 直接 还是通过其他用户 间接 。
最初，用户里没有人是其他用户的朋友。给你一个下标从 0 开始的二维整数数组 requests 表示好友请求的列表，其中 requests[j] = [uj, vj] 是用户 uj 和用户 vj 之间的一条好友请求。
如果 uj 和 vj 可以成为 朋友 ，那么好友请求将会 成功 。每个好友请求都会按列表中给出的顺序进行处理（即，requests[j] 会在 requests[j + 1] 前）。一旦请求成功，那么对所有未来的好友请求而言， uj 和 vj 将会 成为直接朋友 。
返回一个 布尔数组 result ，其中元素遵循此规则：如果第 j 个好友请求 成功 ，那么 result[j] 就是 true ；否则，为 false 。
注意：如果 uj 和 vj 已经是直接朋友，那么他们之间的请求将仍然 成功 。
示例 1：
输入：n = 3, restrictions = [[0,1]], requests = [[0,2],[2,1]] 输出：[true,false] 解释： 请求 0 ：用户 0 和 用户 2 可以成为朋友，所以他们成为直接朋友。 请求 1 ：用户 2 和 用户 1 不能成为朋友，因为这会使 用户 0 和 用户 1 成为间接朋友 (1--2--0) 。
示例 2：
输入：n = 3, restrictions = [[0,1]], requests = [[1,2],[0,2]] 输出：[true,false] 解释： 请求 0 ：用户 1 和 用户 2 可以成为朋友，所以他们成为直接朋友。 请求 1 ：用户 0 和 用户 2 不能成为朋友，因为这会使 用户 0 和 用户 1 成为间接朋友 (0--2--1) 。
示例 3：
输入：n = 5, restrictions = [[0,1],[1,2],[2,3]], requests = [[0,4],[1,2],[3,1],[3,4]] 输出：[true,false,true,false] 解释： 请求 0 ：用户 0 和 用户 4 可以成为朋友，所以他们成为直接朋友。 请求 1 ：用户 1 和 用户 2 不能成为朋友，因为他们之间存在限制。 请求 2 ：用户 3 和 用户 1 可以成为朋友，所以他们成为直接朋友。 请求 3 ：用户 3 和 用户 4 不能成为朋友，因为这会使 用户 0 和 用户 1 成为间接朋友 (0--4--3--1) 。
提示：
2 <= n <= 10000 <= restrictions.length <= 1000restrictions[i].length == 20 <= xi, yi <= n - 1xi != yi1 <= requests.length <= 1000requests[j].length == 20 <= uj, vj <= n - 1uj != vj
解题思路
方法一：并查集
我们可以用并查集来维护朋友关系，然后对于每个请求，判断是否满足限制条件。
对于当前请求的两个人 ，如果他们已经是朋友，那么可以直接接受请求；否则，我们遍历限制条件，如果存在限制条件 ，使得 和 互为朋友并且 和 互为朋友，或者 和 互为朋友并且 和 互为朋友，那么就不能接受请求。
时间复杂度 ，空间复杂度 。其中 和 分别是请求的数量和限制条件的数量。
class Solution:
def friendRequests(
self, n: int, restrictions: List[List[int]], requests: List[List[int]]
) -> List[bool]:
def find(x: int) -> int:
if p[x] != x:
p[x] = find(p[x])
return p[x]
p = list(range(n))
ans = []
for u, v in requests:
pu, pv = find(u), find(v)
if pu == pv:
ans.append(True)
else:
ok = True
for x, y in restrictions:
px, py = find(x), find(y)
if (pu == px and pv == py) or (pu == py and pv == px):
ok = False
break
ans.append(ok)
if ok:
p[pu] = pv
return ans
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity depends on the number of requests times the number of restrictions, optimized using union-find with path compression. Space complexity is mainly the union-find arrays for parent and rank structures. |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Pay attention to indirect friendships that may violate restrictions.
- question_mark
Consider union-find optimizations for fast component lookups.
- question_mark
Clarify how restrictions affect both direct and indirect connections.
常见陷阱
外企场景- error
Failing to account for indirect friendship violations through multiple connected people.
- error
Updating union-find incorrectly, leading to incorrect future checks.
- error
Assuming requests can always be accepted if no direct restriction exists.
进阶变体
外企场景- arrow_right_alt
Restrictions may be asymmetric, requiring careful union-find checks.
- arrow_right_alt
Requests can arrive in random order, increasing the importance of efficient checking.
- arrow_right_alt
The network could grow dynamically, testing union-find scaling under frequent updates.