Hard
题目描述
给你一个整数 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，其中 result[j] 是 true，如果第 j 个朋友请求是成功的，否则为 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
解题思路
这道题的核心思路是使用并查集来维护朋友关系，同时在每次合并操作前检查是否会违反限制条件。
基本思路：
并查集维护朋友关系：使用并查集来表示朋友网络，同一个连通分量中的所有人都是间接朋友关系。
检查限制条件：对于每个朋友请求
[u, v]，我们需要检查合并u和v所在的连通分量后，是否会让某个限制对[x, y]中的x和y处于同一个连通分量。模拟合并过程：为了避免实际修改并查集状态，我们可以创建一个临时的并查集副本，在其上模拟合并操作，检查是否违反限制。
算法步骤：
- 初始化并查集，每个人最初都是独立的连通分量
- 对于每个请求
[u, v]：- 如果
u和v已经在同一个连通分量，直接返回true - 否则创建并查集的副本，模拟合并
u和v - 检查所有限制对，看是否有受限的两人会在合并后处于同一连通分量
- 如果没有违反限制，则执行真正的合并操作，记录结果为
true - 如果违反限制，记录结果为
false
- 如果
这种方法的时间复杂度相对较高但思路清晰，适合题目给定的数据规模。
代码实现
class Solution {
public:
vector<int> parent;
int find(int x) {
if (parent[x] != x) {
parent[x] = find(parent[x]);
}
return parent[x];
}
void unite(int x, int y) {
int px = find(x), py = find(y);
if (px != py) {
parent[px] = py;
}
}
bool connected(int x, int y) {
return find(x) == find(y);
}
vector<bool> friendRequests(int n, vector<vector<int>>& restrictions, vector<vector<int>>& requests) {
parent.resize(n);
iota(parent.begin(), parent.end(), 0);
vector<bool> result;
for (auto& req : requests) {
int u = req[0], v = req[1];
// 如果已经是朋友，直接成功
if (connected(u, v)) {
result.push_back(true);
continue;
}
// 创建临时并查集来模拟合并
vector<int> tempParent = parent;
parent = tempParent;
unite(u, v);
// 检查是否违反限制
bool valid = true;
for (auto& restriction : restrictions) {
int x = restriction[0], y = restriction[1];
if (connected(x, y)) {
valid = false;
break;
}
}
if (valid) {
result.push_back(true);
// 保持合并后的状态
} else {
result.push_back(false);
// 恢复原状态
parent = tempParent;
}
}
return result;
}
};
class Solution:
def friendRequests(self, n: int, restrictions: List[List[int]], requests: List[List[int]]) -> List[bool]:
parent = list(range(n))
def find(x):
if parent[x] != x:
parent[x] = find(parent[x])
return parent[x]
def unite(x, y):
px, py = find(x), find(y)
if px != py:
parent[px] = py
def connected(x, y):
return find(x) == find(y)
result = []
for u, v in requests:
# 如果已经是朋友，直接成功
if connected(u, v):
result.append(True)
continue
# 创建临时并查集来模拟合并
temp_parent = parent[:]
unite(u, v)
# 检查是否违反限制
valid = True
for x, y in restrictions:
if connected(x, y):
valid = False
break
if valid:
result.append(True)
# 保持合并后的状态
else:
result.append(False)
# 恢复原状态
parent = temp_parent
return result
public class Solution {
private int[] parent;
private int Find(int x) {
if (parent[x] != x) {
parent[x] = Find(parent[x]);
}
return parent[x];
}
private void Unite(int x, int y) {
int px = Find(x), py = Find(y);
if (px != py) {
parent[px] = py;
}
}
private bool Connected(int x, int y) {
return Find(x) == Find(y);
}
public bool[] FriendRequests(int n, int[][] restrictions, int[][] requests) {
parent = new int[n];
for (int i = 0; i < n; i++) {
parent[i] = i;
}
List<bool> result = new List<bool>();
foreach (var req in requests) {
int u = req[0], v = req[1];
// 如果已经是朋友，直接成功
if (Connected(u, v)) {
result.Add(true);
continue;
}
// 创建临时并查集来模拟合并
int[] tempParent = new int[n];
Array.Copy(parent, tempParent, n);
Unite(u, v);
// 检查是否违反限制
bool valid = true;
foreach (var restriction in restrictions) {
int x = restriction[0], y = restriction[1];
if (Connected(x, y)) {
valid = false;
break;
}
}
if (valid) {
result.Add(true);
// 保持合并后的状态
} else {
result.Add(false);
// 恢复原状态
parent = tempParent;
}
}
return result.ToArray();
}
}
var friendRequests = function(n, restrictions, requests) {
class UnionFind {
constructor(n) {
this.parent = Array.from({length: n}, (_, i) => i);
this.rank = new Array(n).fill(0);
}
find(x) {
if (this.parent[x] !== x) {
this.parent[x] = this.find(this.parent[x]);
}
return this.parent[x];
}
union(x, y) {
let rootX = this.find(x);
let rootY = this.find(y);
if (rootX === rootY) return;
if (this.rank[rootX] < this.rank[rootY]) {
this.parent[rootX] = rootY;
} else if (this.rank[rootX] > this.rank[rootY]) {
this.parent[rootY] = rootX;
} else {
this.parent[rootY] = rootX;
this.rank[rootX]++;
}
}
connected(x, y) {
return this.find(x) === this.find(y);
}
copy() {
let newUF = new UnionFind(this.parent.length);
newUF.parent = [...this.parent];
newUF.rank = [...this.rank];
return newUF;
}
}
let uf = new UnionFind(n);
let result = [];
for (let [u, v] of requests) {
let tempUF = uf.copy();
tempUF.union(u, v);
let valid = true;
for (let [x, y] of restrictions) {
if (tempUF.connected(x, y)) {
valid = false;
break;
}
}
if (valid) {
uf.union(u, v);
result.push(true);
} else {
result.push(false);
}
}
return result;
};
复杂度分析
| 复杂度类型 | 分析 |
|---|---|
| 时间复杂度 | O(requests.length × restrictions.length × α(n))，其中 α(n) 是反阿克曼函数，对于每个请求需要检查所有限制条件 |
| 空间复杂度 | O(n)，并查集需要 O(n) 空间，临时数组也需要 O(n) 空间 |