Welcome to Subscribe On Youtube

2076. Process Restricted Friend Requests

Description

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

Solutions

  • 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];
        }
    }
    
  • class Solution {
    public:
        vector<int> p;
    
        vector<bool> friendRequests(int n, vector<vector<int>>& restrictions, vector<vector<int>>& requests) {
            p.resize(n);
            for (int i = 0; i < n; ++i) p[i] = i;
            vector<bool> ans;
            for (auto& req : requests) {
                int u = req[0], v = req[1];
                if (find(u) == find(v))
                    ans.push_back(true);
                else {
                    bool valid = true;
                    for (auto& 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;
                        }
                    }
                    ans.push_back(valid);
                    if (valid) p[find(u)] = find(v);
                }
            }
            return ans;
        }
    
        int find(int x) {
            if (p[x] != x) p[x] = find(p[x]);
            return p[x];
        }
    };
    
  • 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
    
    
  • 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]
    }
    

All Problems

All Solutions