2076

2076. Process Restricted Friend Requests (Hard)

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

Similar Questions:

• Number of Islands II (Hard)
• Smallest String With Swaps (Medium)

Solution 1. Union Find

Given the constraints, a solution with O(R * B) is acceptable -- for each request, check if it obeys all the bans.

For the check, we can do it in O(1) time using UnionFind. For each prior valid requests, we connect the two friends. For a new request, we just need to check if the leaders of the two parties are in any of those bans.

// OJ: https://leetcode.com/problems/process-restricted-friend-requests/
// Author: github.com/lzl124631x
// Time: O(R * B) where `R`/`B` is the length of `requests`/`bans`
// Space: O(N)
class UnionFind {
    vector<int> id;
public:
    UnionFind(int n) : id(n) {
        iota(begin(id), end(id), 0);
    }
    void connect(int a, int b) {
        id[find(a)] = find(b);
    }
    int find(int a) {
        return id[a] == a ? a : (id[a] = find(id[a]));
    }
    int connected(int a, int b) {
        return find(a) == find(b);
    }
};
class Solution {
public:
    vector<bool> friendRequests(int n, vector<vector<int>>& bans, vector<vector<int>>& requests) {
        vector<bool> ans;
        UnionFind uf(n);
        for (auto &r : requests) {
            int p = uf.find(r[0]), q = uf.find(r[1]); // the leaders of the two parties
            bool valid = true;
            if (!uf.connected(p, q)) { // Only need to check the bans if the two parties are not already connected
                for (auto &b : bans) {
                    int x = uf.find(b[0]), y = uf.find(b[1]); // the leaders of the two banned parties
                    if ((x == p && y == q) || (x == q && y == p)) {
                        valid = false;
                        break;
                    }
                }
            }
            ans.push_back(valid);
            if (valid) uf.connect(p, q); // connect two parties if request is valid
        }
        return ans;
    }
};

Discuss

https://leetcode.com/problems/process-restricted-friend-requests/discuss/1576935/C%2B%2B-Union-Find