处理含限制条件的好友请求

2076. 处理含限制条件的好友请求

给你一个整数 n ，表示网络上的用户数目。每个用户按从 0 到 n - 1 进行编号。

给你一个下标从 0 开始的二维整数数组 restrictions ，其中 restrictions[i] = [x_i, y_i] 意味着用户 x_i 和用户 y_i 不能成为朋友，不管是直接还是通过其他用户间接。

最初，用户里没有人是其他用户的朋友。给你一个下标从 0 开始的二维整数数组 requests 表示好友请求的列表，其中 requests[j] = [u_j, v_j] 是用户 u_j 和用户 v_j 之间的一条好友请求。

如果 u_j 和 v_j 可以成为朋友，那么好友请求将会成功。每个好友请求都会按列表中给出的顺序进行处理（即，requests[j] 会在 requests[j + 1] 前）。一旦请求成功，那么对所有未来的好友请求而言， u_j 和 v_j 将会 成为直接朋友。

返回一个 布尔数组 result ，其中元素遵循此规则：如果第 j 个好友请求成功，那么 result[j] 就是 true ；否则，为 false 。

注意：如果 u_j 和 v_j 已经是直接朋友，那么他们之间的请求将仍然成功。

示例 1：

输入：n = 3, restrictions = [[0,1]], requests = [[0,2],[2,1]]
输出：[true,false]
解释：
请求 0 ：用户 0 和 用户 2 可以成为朋友，所以他们成为直接朋友。 
请求 1 ：用户 2 和 用户 1 不能成为朋友，因为这会使 用户 0 和 用户 1 成为间接朋友 (1--2--0) 。

示例 2：

输入：n = 3, restrictions = [[0,1]], requests = [[1,2],[0,2]]
输出：[true,false]
解释：
请求 0 ：用户 1 和 用户 2 可以成为朋友，所以他们成为直接朋友。 
请求 1 ：用户 0 和 用户 2 不能成为朋友，因为这会使 用户 0 和 用户 1 成为间接朋友 (0--2--1) 。

示例 3：

输入：n = 5, restrictions = [[0,1],[1,2],[2,3]], requests = [[0,4],[1,2],[3,1],[3,4]]
输出：[true,false,true,false]
解释：
请求 0 ：用户 0 和 用户 4 可以成为朋友，所以他们成为直接朋友。 
请求 1 ：用户 1 和 用户 2 不能成为朋友，因为他们之间存在限制。
请求 2 ：用户 3 和 用户 1 可以成为朋友，所以他们成为直接朋友。 
请求 3 ：用户 3 和 用户 4 不能成为朋友，因为这会使 用户 0 和 用户 1 成为间接朋友 (0--4--3--1) 。

提示：

2 <= n <= 1000
0 <= restrictions.length <= 1000
restrictions[i].length == 2
0 <= x_i, y_i <= n - 1
x_i != y_i
1 <= requests.length <= 1000
requests[j].length == 2
0 <= u_j, v_j <= n - 1
u_j != v_j

原站题解

去查看

上次编辑到这里，代码来自缓存点击恢复默认模板

class Solution { public: vector<bool> friendRequests(int n, vector<vector<int>>& restrictions, vector<vector<int>>& requests) { } };

java 解法, 执行用时: 8 ms, 内存消耗: 43.4 MB, 提交时间: 2023-09-17 12:16:19

class Solution {
    private int[] pre;
    private boolean[][] res;
    public boolean[] friendRequests(int n, int[][] restrictions, int[][] requests) {
        pre = new int[n];
        res = new boolean[n][n];
        for(int i=0; i<n; i++){
            pre[i] = i;
        }
        int r=restrictions.length;
        for(int i=0; i<r; i++){
            int x=restrictions[i][0],y=restrictions[i][1];
            res[x][y] = true;
            res[y][x] = true;
        }
        int m=requests.length;
        boolean[] ans = new boolean[m];
        for(int i=0; i<m; i++){
            int x=find(requests[i][0]), y=find(requests[i][1]);
            if(x == y){
                ans[i] = true;
            }else{
                if(res[x][y] || res[y][x]){
                    ans[i] = false;
                }else{
                    pre[x] = y;
                    for(int j=0; j<n; j++){
                        if(res[x][j]){
                            res[y][j] = true;
                            res[j][y] = true;
                        }
                    }
                    ans[i] = true;
                }
            }
        }
        return ans;
    }
    
    public int find(int x){
        int r = x;
        while(pre[r] != r){
            r = pre[r];
        }
        int i=x, j;
        while(i != r){
            j = pre[i];
            pre[i] = r;
            i = j;
        }
        return r;
    }
}

python3 解法, 执行用时: 108 ms, 内存消耗: 37.7 MB, 提交时间: 2023-09-17 12:15:52

class UnionSet():
    def __init__(self, n: int):
        self.parent = [i for i in range(n)]
        self.blacklist = [set() for i in range(n)]
        self.members = [{i} for i in range(n)]
    def find(self, x: int) -> int:
        if x != self.parent[x]:
            new_parent = self.find(self.parent[x])
            self.parent[x] = new_parent
            self.blacklist[new_parent] |= self.blacklist[x]
            self.members[new_parent] |= self.members[x]
        return self.parent[x]
    def union(self, x: int, y: int):
        px, py = self.find(x), self.find(y)
        if (self.blacklist[px] & self.members[py]) or (self.blacklist[py] & self.members[px]):
            return False
        else:
            self.parent[py] = px
            self.blacklist[px] |= self.blacklist[py]
            self.members[px] |= self.members[py]
            return True

class Solution:
    def friendRequests(self, n: int, restrictions: List[List[int]], requests: List[List[int]]) -> List[bool]:
        u = UnionSet(n)
        for a, b in restrictions:
            u.blacklist[a].add(b)
            u.blacklist[b].add(a)
        return [u.union(a, b) for a, b in requests]

cpp 解法, 执行用时: 68 ms, 内存消耗: 34.9 MB, 提交时间: 2023-09-17 12:15:28

class Solution {
    // 每个人都有一个“大哥”
    vector<int> parent;
    // 我们可以通过`root()`函数递归找到这个圈子里最大的大哥，也就是圈子的头头。
    // 头头没有大哥（parent[x] == -1），或者他的大哥就是他自己（parent[x] == x）
    int root(int x) { return (parent[x] == -1 || parent[x] == x) ? x : root(parent[x]); };
public:
    vector<bool> friendRequests(int n, vector<vector<int>>& restrictions, vector<vector<int>>& requests) {
        // 维护自己朋友圈的朋友名单`friends`，
        vector<unordered_set<int>> friends(n);
        for (int i = 0; i < n; i++) {
            friends[i].insert(i);
        }
        // 维护自己朋友圈的仇人名单`enemies`，
        vector<unordered_set<int>> enemies(n);
        for (auto& res : restrictions) {
            enemies[res[0]].insert(res[1]);
            enemies[res[1]].insert(res[0]);
        }  
        // 开始的时候大家都没有大哥（-1）
        parent = vector<int>(n, -1);
        auto requests_size = requests.size();
        // 我们假定所有交友请求都能成功
        vector<bool> result(requests_size, true);
        for (int i = 0; i < requests_size; i++) {
            // 对于每个交友请求`requests[i]`，先找到两个圈子的头头x和y。
            int x = root(requests[i][0]), y = root(requests[i][1]);
            // 如果头头是同一个人，说明是同一个圈子。
            if (x == y) continue;
            // 我判断大哥的方式很粗暴，谁的朋友多谁就是大哥。
            // 这是因为后面要遍历friends[y]，保证friends[y]的数量比friends[x]小可以提高速度。
            if (friends[x].size() < friends[y].size()) swap(x, y);
            [&]{
                // 头头`x`首先查看`y`提交的朋友名单`friends[y]`
                for (auto people : friends[y]) {
                    // 如果有一个`people`出现在`x`维护的仇人名单`enemies[x]`中
                    if (enemies[x].count(people) != 0) {
                        // 交朋友就失败了
                        result[i] = false;
                        // 立刻滚蛋（相当于goto匿名函数末尾）
                        return;
                    }
                }
                // `x`把`y`上交的仇人名单`enemies[y]`添加到自己的仇人名单里。
                enemies[x].insert(enemies[y].begin(), enemies[y].end());
                // `x`把`y`上交的朋友名单`friends[y]`添加到自己的朋友名单里。
                friends[x].insert(friends[y].begin(), friends[y].end());
                // `y`拜`x`为大哥，这样，`y`的小弟们都会跟着认`x`为头头。
                parent[y] = x;
            }();
        }
        return result;
    }
};

golang 解法, 执行用时: 36 ms, 内存消耗: 6.9 MB, 提交时间: 2023-09-17 12:15:01

/**
 * 用并查集维护朋友关系。同时我们还要处理哪些用户不能成为朋友，这可以用哈希表来维护。
 * 更具体地，我们可以在并查集的代表元（即 find 的终点）上记录当前集合与哪些用户不能成为朋友。
 * 如果两个用户不在同一集合且可以成为朋友，那么就要用并查集合并这两个集合，
 * 同时把与其中一个集合的不能成为朋友的用户添加到另一个集合上。这里的一个优化点是，
 * 合并集合时，总是从小的集合合并到大的集合上。
 */
func friendRequests(n int, restrictions [][]int, requests [][]int) []bool {
	fa := make([]int, n) // 初始化并查集
	for i := range fa {
		fa[i] = i
	}
	var find func(int) int
	find = func(x int) int {
		if fa[x] != x {
			fa[x] = find(fa[x])
		}
		return fa[x]
	}

	cant := make([]map[int]bool, n)
	for i := range cant {
		cant[i] = map[int]bool{}
	}
	for _, r := range restrictions { // 初始化无法成为朋友的用户
		v, w := r[0], r[1]
		cant[v][w] = true
		cant[w][v] = true // 双向
	}

	ans := make([]bool, len(requests))
	for i, r := range requests {
		v, w := find(r[0]), find(r[1])
		if v == w { // 已经是朋友（直接或间接）
			ans[i] = true
			continue
		}
		if cant[v][w] { // 无法成为朋友
			continue
		}
		ans[i] = true
		if len(cant[v]) > len(cant[w]) { // 启发式合并：总是从小的集合合并到大的集合上
			v, w = w, v
		}
		for x := range cant[v] { // 将 cant[v] 中的代表元合并到 cant[w] 上
			x = find(x)
			cant[w][x] = true
			cant[x][w] = true // 双向
		}
		fa[v] = w
	}
	return ans
}

上一题

下一题

详情