文章目录
1. 题目
2. 解题
1. 题目
给你一个整数 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 <= 1000 0 <= restrictions.length <= 1000 restrictions[i].length == 2 0 <= xi, yi <= n - 1 xi != yi 1 <= requests.length <= 1000 requests[j].length == 2 0 <= uj, vj <= n - 1 uj != vj
2. 解题
参考：数据结构 并查集
使用并查集维护好友关系
对于每次的请求[a, b]，查找请求两端的代表 fa，fb，遍历所有的限制条件 [r0, r1]，也查找其代表 f0, f1，如果能匹配上 (fa==f0 && fb==f1) || (fa==f1 && fb==f0)，则他们不能连通
class dsu{ vector<int> f; public: dsu(int n) { f.resize(n); for(int i = 0; i < n; ++i) f[i] = i; } void merge(int a, int b) { if(!isfriend(a, b)) f[a] = b; } int find(int a) { if(f[a] == a) return a; return f[a] = find(f[a]); } bool isfriend(int a, int b) { int fa = find(a), fb = find(b); return fa==fb; } }; class Solution { public: vector<bool> friendRequests(int n, vector<vector<int>>& restrictions, vector<vector<int>>& requests) { dsu u(n);//并查集 vector<bool> ans(requests.size(), true); for(int i = 0; i < requests.size(); ++i) { int a = requests[i][0], b = requests[i][1]; if(u.isfriend(a, b)) continue; int fa = u.find(a), fb = u.find(b); bool flag = true; for(auto& r : restrictions) { int f0 = u.find(r[0]), f1 = u.find(r[1]); if((fa==f0 && fb==f1) || (fa==f1 && fb==f0)) { flag = false; break; } } ans[i] = flag; // if(flag) u.merge(a, b); // 错误解 if(flag) u.merge(fa, fb); // 正确的解，把最顶层的父节点合并 } return ans; } };
256 ms 21.4 MB C++
