Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/2076.html

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:

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/
    // 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;
        }
    };
    
  • class Solution:
        def friendRequests(
            self, n: int, restrictions: List[List[int]], requests: List[List[int]]
        ) -> List[bool]:
            p = list(range(n))
    
            def find(x):
                if p[x] != x:
                    p[x] = find(p[x])
                return p[x]
    
            ans = []
            i = 0
            for u, v in requests:
                if find(u) == find(v):
                    ans.append(True)
                else:
                    valid = True
                    for x, y in restrictions:
                        if (find(u) == find(x) and find(v) == find(y)) or (
                            find(u) == find(y) and find(v) == find(x)
                        ):
                            valid = False
                            break
                    ans.append(valid)
                    if valid:
                        p[find(u)] = find(v)
            return ans
    
    ############
    
    # 2076. Process Restricted Friend Requests
    # https://leetcode.com/problems/process-restricted-friend-requests
    
    class DSU:
        def __init__(self, n):
            self.graph = list(range(n))
        
        def find(self, x):
            if self.graph[x] != x:
                self.graph[x] = self.find(self.graph[x])
            
            return self.graph[x]
        
        def union(self, x, y):
            px = self.find(x)
            py = self.find(y)
            
            self.graph[px] = py
    
    class Solution:
        def friendRequests(self, n: int, restrictions: List[List[int]], requests: List[List[int]]) -> List[bool]:
            dsu = DSU(n)
            res = []
            
            for x, y in requests:
                px, py = dsu.find(x), dsu.find(y)
                valid = True
                
                for a, b in restrictions:
                    pa, pb = dsu.find(a), dsu.find(b)
                    
                    if set([pa, pb]) == set([px, py]):
                        valid = False
                        break
                
                res.append(valid)
                if valid:
                    dsu.union(x, y)
            
            return res
    
    
  • class Solution {
        private int[] p;
    
        public boolean[] friendRequests(int n, int[][] restrictions, int[][] requests) {
            p = new int[n];
            for (int i = 0; i < n; ++i) {
                p[i] = i;
            }
            boolean[] ans = new boolean[requests.length];
            int i = 0;
            for (int[] req : requests) {
                int u = req[0], v = req[1];
                if (find(u) == find(v)) {
                    ans[i++] = true;
                } else {
                    boolean valid = true;
                    for (int[] res : restrictions) {
                        int x = res[0], y = res[1];
                        if ((find(u) == find(x) && find(v) == find(y))
                            || (find(u) == find(y) && find(v) == find(x))) {
                            valid = false;
                            break;
                        }
                    }
                    if (valid) {
                        p[find(u)] = find(v);
                        ans[i++] = true;
                    } else {
                        ans[i++] = false;
                    }
                }
            }
            return ans;
        }
    
        private int find(int x) {
            if (p[x] != x) {
                p[x] = find(p[x]);
            }
            return p[x];
        }
    }
    
  • var p []int
    
    func friendRequests(n int, restrictions [][]int, requests [][]int) []bool {
    	p = make([]int, n)
    	for i := 0; i < n; i++ {
    		p[i] = i
    	}
    	var ans []bool
    	for _, req := range requests {
    		u, v := req[0], req[1]
    		if find(u) == find(v) {
    			ans = append(ans, true)
    		} else {
    			valid := true
    			for _, res := range restrictions {
    				x, y := res[0], res[1]
    				if (find(u) == find(x) && find(v) == find(y)) || (find(u) == find(y) && find(v) == find(x)) {
    					valid = false
    					break
    				}
    			}
    			ans = append(ans, valid)
    			if valid {
    				p[find(u)] = find(v)
    			}
    		}
    	}
    	return ans
    }
    
    func find(x int) int {
    	if p[x] != x {
    		p[x] = find(p[x])
    	}
    	return p[x]
    }
    

Discuss

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

All Problems

All Solutions