{"id":8719,"date":"2021-11-15T13:04:13","date_gmt":"2021-11-15T21:04:13","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=8719"},"modified":"2021-11-15T13:05:03","modified_gmt":"2021-11-15T21:05:03","slug":"leetcode-2076-process-restricted-friend-requests","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/graph\/leetcode-2076-process-restricted-friend-requests\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 2076. Process Restricted Friend Requests"},"content":{"rendered":"\n

You are given an integer n<\/code> indicating the number of people in a network. Each person is labeled from 0<\/code> to n - 1<\/code>.<\/p>\n\n\n\n

You are also given a 0-indexed<\/strong> 2D integer array restrictions<\/code>, where restrictions[i] = [xi<\/sub>, yi<\/sub>]<\/code> means that person xi<\/sub><\/code> and person yi<\/sub><\/code> cannot <\/strong>become friends<\/strong>,either directly<\/strong> or indirectly<\/strong> through other people.<\/p>\n\n\n\n

Initially, no one is friends with each other. You are given a list of friend requests as a 0-indexed<\/strong> 2D integer array requests<\/code>, where requests[j] = [uj<\/sub>, vj<\/sub>]<\/code> is a friend request between person uj<\/sub><\/code> and person vj<\/sub><\/code>.<\/p>\n\n\n\n

A friend request is successful <\/strong>if uj<\/sub><\/code> and vj<\/sub><\/code> can be friends<\/strong>. Each friend request is processed in the given order (i.e., requests[j]<\/code> occurs before requests[j + 1]<\/code>), and upon a successful request, uj<\/sub><\/code> and vj<\/sub><\/code> become direct friends<\/strong> for all future friend requests.<\/p>\n\n\n\n

Return a boolean array<\/strong> <\/em>result<\/code>, where each <\/em>result[j]<\/code> is <\/em>true<\/code> if the <\/em>jth<\/sup><\/code> friend request is successful<\/strong> or <\/em>false<\/code> if it is not<\/em>.<\/p>\n\n\n\n

Note:<\/strong> If uj<\/sub><\/code> and vj<\/sub><\/code> are already direct friends, the request is still successful<\/strong>.<\/p>\n\n\n\n

Example 1:<\/strong><\/p>\n\n\n\n

Input:<\/strong> n = 3, restrictions = [[0,1]], requests = [[0,2],[2,1]]\nOutput:<\/strong> [true,false]\nExplanation:\n<\/strong>Request 0: Person 0 and person 2 can be friends, so they become direct friends. \nRequest 1: Person 2 and person 1 cannot be friends since person 0 and person 1 would be indirect friends (1--2--0).\n<\/pre>\n\n\n\n
Example 2:<\/strong><\/p>\n\n\n\n
Input:<\/strong> n = 3, restrictions = [[0,1]], requests = [[1,2],[0,2]]\nOutput:<\/strong> [true,false]\nExplanation:\n<\/strong>Request 0: Person 1 and person 2 can be friends, so they become direct friends.\nRequest 1: Person 0 and person 2 cannot be friends since person 0 and person 1 would be indirect friends (0--2--1).\n<\/pre>\n\n\n\n
Example 3:<\/strong><\/p>\n\n\n\n
Input:<\/strong> n = 5, restrictions = [[0,1],[1,2],[2,3]], requests = [[0,4],[1,2],[3,1],[3,4]]\nOutput:<\/strong> [true,false,true,false]\nExplanation:\n<\/strong>Request 0: Person 0 and person 4 can be friends, so they become direct friends.\nRequest 1: Person 1 and person 2 cannot be friends since they are directly restricted.\nRequest 2: Person 3 and person 1 can be friends, so they become direct friends.\nRequest 3: Person 3 and person 4 cannot be friends since person 0 and person 1 would be indirect friends (0--4--3--1).\n<\/pre>\n\n\n\n
Constraints:<\/strong><\/p>\n\n\n\n
  • 2 <= n <= 1000<\/code><\/li>
  • 0 <= restrictions.length <= 1000<\/code><\/li>
  • restrictions[i].length == 2<\/code><\/li>
  • 0 <= xi<\/sub>, yi<\/sub> <= n - 1<\/code><\/li>
  • xi<\/sub> != yi<\/sub><\/code><\/li>
  • 1 <= requests.length <= 1000<\/code><\/li>
  • requests[j].length == 2<\/code><\/li>
  • 0 <= uj<\/sub>, vj<\/sub> <= n - 1<\/code><\/li>
  • uj<\/sub> != vj<\/sub><\/code><\/li><\/ul>\n\n\n\n
    Solution: Union Find \/ Brute Force<\/strong><\/p>\n\n\n\n
    For each request, check all restrictions.<\/p>\n\n\n\n
    Time complexity: O(req * res)
    Space complexity: O(n)<\/p>\n\n\n\n
    \n
    C++<\/h2>\n
    \n\n
    \n\/\/ Author: Huahua\nclass Solution {\npublic:\n  vector friendRequests(int n, vector>& restrictions, vector>& requests) {\n    vector parents(n);\n    iota(begin(parents), end(parents), 0);\n    function find = [&](int x) {\n      if (parents[x] == x) return x;\n      return parents[x] = find(parents[x]);\n    };\n    auto check = [&](int u, int v) {\n      for (const auto& r : restrictions) {\n        int pu = find(r[0]);\n        int pv = find(r[1]);\n        if ((pu == u && pv == v) || (pu == v && pv == u))\n          return false;\n      }\n      return true;\n    };\n    vector ans;\n    for (const auto& r : requests) {      \n      int pu = find(r[0]);\n      int pv = find(r[1]);\n      if (pu == pv || check(pu, pv)) {\n        parents[pu] = pv;\n        ans.push_back(true);\n      } else {\n        ans.push_back(false);\n      }\n    }\n    return ans;\n  }\n};\n<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"
    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…<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[76],"tags":[77,217,113],"class_list":["post-8719","post","type-post","status-publish","format-standard","hentry","category-graph","tag-graph","tag-hard","tag-union-find","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/8719","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/comments?post=8719"}],"version-history":[{"count":2,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/8719\/revisions"}],"predecessor-version":[{"id":8721,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/8719\/revisions\/8721"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=8719"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=8719"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=8719"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}