You are given an integer n
indicating the number of people in a network. Each person is labeled from 0
to n - 1
.
You are also given a 0-indexed 2D integer array restrictions
, where restrictions[i] = [xi, yi]
means that person xi
and person yi
cannot become friends,either directly or indirectly through other people.
Initially, no one is friends with each other. You are given a list of friend requests as a 0-indexed 2D integer array requests
, where requests[j] = [uj, vj]
is a friend request between person uj
and person vj
.
A friend request is successful if uj
and vj
can be friends. Each friend request is processed in the given order (i.e., requests[j]
occurs before requests[j + 1]
), and upon a successful request, uj
and vj
become direct friends for all future friend requests.
Return a boolean array result
, where each result[j]
is true
if the jth
friend request is successful or false
if it is not.
Note: If uj
and vj
are already direct friends, the request is still successful.
Example 1:
Input: n = 3, restrictions = [[0,1]], requests = [[0,2],[2,1]] Output: [true,false] Explanation: Request 0: Person 0 and person 2 can be friends, so they become direct friends. Request 1: Person 2 and person 1 cannot be friends since person 0 and person 1 would be indirect friends (1--2--0).
Example 2:
Input: n = 3, restrictions = [[0,1]], requests = [[1,2],[0,2]] Output: [true,false] Explanation: Request 0: Person 1 and person 2 can be friends, so they become direct friends. Request 1: Person 0 and person 2 cannot be friends since person 0 and person 1 would be indirect friends (0--2--1).
Example 3:
Input: n = 5, restrictions = [[0,1],[1,2],[2,3]], requests = [[0,4],[1,2],[3,1],[3,4]] Output: [true,false,true,false] Explanation: Request 0: Person 0 and person 4 can be friends, so they become direct friends. Request 1: Person 1 and person 2 cannot be friends since they are directly restricted. Request 2: Person 3 and person 1 can be friends, so they become direct friends. Request 3: Person 3 and person 4 cannot be friends since person 0 and person 1 would be indirect friends (0--4--3--1).
Constraints:
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
Solution: Union Find / Brute Force
For each request, check all restrictions.
Time complexity: O(req * res)
Space complexity: O(n)
C++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 |
// Author: Huahua class Solution { public: vector<bool> friendRequests(int n, vector<vector<int>>& restrictions, vector<vector<int>>& requests) { vector<int> parents(n); iota(begin(parents), end(parents), 0); function<int(int)> find = [&](int x) { if (parents[x] == x) return x; return parents[x] = find(parents[x]); }; auto check = [&](int u, int v) { for (const auto& r : restrictions) { int pu = find(r[0]); int pv = find(r[1]); if ((pu == u && pv == v) || (pu == v && pv == u)) return false; } return true; }; vector<bool> ans; for (const auto& r : requests) { int pu = find(r[0]); int pv = find(r[1]); if (pu == pv || check(pu, pv)) { parents[pu] = pv; ans.push_back(true); } else { ans.push_back(false); } } return ans; } }; |
请尊重作者的劳动成果,转载请注明出处!花花保留对文章/视频的所有权利。
如果您喜欢这篇文章/视频,欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Be First to Comment