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

Raphael Liu Lv10
  2023-09-13 00:47:26 2023-09-13 00:47:26 Created   2023-09-13 16:06:29 2023-09-13 16:06:29 Updated    

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

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

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

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

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

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

示例 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 <= xi, yi <= n - 1
  • xi != yi
  • 1 <= requests.length <= 1000
  • requests[j].length == 2
  • 0 <= uj, vj <= n - 1
  • uj != vj

方法一：并查集

思路与算法

我们可以使用并查集维护朋友关系。

我们依次处理每一条好友请求。对于请求 [x_i, y_i]，记 x_i 和 y_i 在并查集中的代表元素为 x 和 y，那么：

  • 如果 x = y，那么它们 x_i 和 y_i 在之前已经是朋友了，这条好友请求也一定会成功；

  • 如果 x \neq y，那么我们需要判断这条好友请求是否会违反规则，因此还需要枚举所有的限制。

    对于限制 [u_j, v_j]，记 u_j 和 v_j 在并查集中的代表元素为 u 和 v。在当前好友请求前，一定有 u \neq v，并且我们希望如果当前好友请求成功，u \neq v 仍然成立，所以我们不能将 u 和 v 所在的连通分量合并起来。由于当前好友请求会合并 x 和 y 所在的连通分量，并且 x, y, u, v 均为对应连通分量的代表元素，因此 (x, y) = (u, v) 以及 (y, x) = (v, u) 二者均不能成立，否则合并 x 和 y 所在的连通分量即为合并 u 和 v 所在的连通分量。

    如果所有的限制都满足，那么这条好友请求成功，否则失败。

对于每一条成功的好友请求，我们需要在并查集中将对应的连通分量进行合并。

代码

[sol1-C++]
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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
// 并查集模板
class UnionFind {
public:
    vector<int> parent;
    vector<int> size;
    int n;
    // 当前连通分量数目
    int setCount;
    
public:
    UnionFind(int _n): n(_n), setCount(_n), parent(_n), size(_n, 1) {
        iota(parent.begin(), parent.end(), 0);
    }
    
    int findset(int x) {
        return parent[x] == x ? x : parent[x] = findset(parent[x]);
    }
    
    bool unite(int x, int y) {
        x = findset(x);
        y = findset(y);
        if (x == y) {
            return false;
        }
        if (size[x] < size[y]) {
            swap(x, y);
        }
        parent[y] = x;
        size[x] += size[y];
        --setCount;
        return true;
    }
    
    bool connected(int x, int y) {
        x = findset(x);
        y = findset(y);
        return x == y;
    }
};

class Solution {
public:
    vector<bool> friendRequests(int n, vector<vector<int>>& restrictions, vector<vector<int>>& requests) {
        UnionFind uf(n);
        vector<bool> ans;
        for (const auto& req: requests) {
            int x = uf.findset(req[0]), y = uf.findset(req[1]);
            if (x != y) {
                bool check = true;
                for (const auto& res: restrictions) {
                    int u = uf.findset(res[0]), v = uf.findset(res[1]);
                    if ((x == u && y == v) || (x == v && y == u)) {
                        check = false;
                        break;
                    }
                }
                if (check) {
                    ans.push_back(true);
                    uf.unite(x, y);
                }
                else {
                    ans.push_back(false);
                }
            }
            else {
                ans.push_back(true);
            }
        }
        return ans;
    }
};
[sol1-Python3]
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
43
44
45
46
47
48
49
50
51
52
53
# 并查集模板
class UnionFind:
    def __init__(self, n: int):
        self.parent = list(range(n))
        self.size = [1] * n
        self.n = n
        # 当前连通分量数目
        self.setCount = n
    
    def findset(self, x: int) -> int:
        if self.parent[x] == x:
            return x
        self.parent[x] = self.findset(self.parent[x])
        return self.parent[x]
    
    def unite(self, x: int, y: int) -> bool:
        x, y = self.findset(x), self.findset(y)
        if x == y:
            return False
        if self.size[x] < self.size[y]:
            x, y = y, x
        self.parent[y] = x
        self.size[x] += self.size[y]
        self.setCount -= 1
        return True
    
    def connected(self, x: int, y: int) -> bool:
        x, y = self.findset(x), self.findset(y)
        return x == y

class Solution:
    def friendRequests(self, n: int, restrictions: List[List[int]], requests: List[List[int]]) -> List[bool]:
        uf = UnionFind(n)
        ans = list()

        for req in requests:
            x, y = uf.findset(req[0]), uf.findset(req[1])
            if x != y:
                check = True
                for res in restrictions:
                    u, v = uf.findset(res[0]), uf.findset(res[1])
                    if (x == u and y == v) or (x == v and y == u):
                        check = False
                        break
                if check:
                    ans.append(True)
                    uf.unite(x, y)
                else:
                    ans.append(False)
            else:
                ans.append(True)
        
        return ans

复杂度分析

  • 时间复杂度：O(mn \cdot \alpha(n))，其中 m 是数组 restrictions 的长度，\alpha(\cdot) 是反阿克曼函数，表示在路径压缩和按秩合并优化下的并查集的单次操作时间复杂度。

  • 空间复杂度：O(n)，即为并查集需要使用的空间。

 Comments
On this page
2076-处理含限制条件的好友请求