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

Solution 1

Python Code
 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

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

Java Code
 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
34
35
36
37
38
39
40
41
42

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];
    }
}

C++ Code
 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

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];
    }
};

Go Code
 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
34
35
36

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]
}