原文链接: https://leetcode-cn.com/problems/process-restricted-friend-requests

英文原文

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] = [x_i, y_i] means that person x_i and person y_i 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] = [u_j, v_j] is a friend request between person u_j and person v_j.

A friend request is successful if u_j and v_j 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, u_j and v_j become direct friends for all future friend requests.

Return a boolean array result, where each result[j] is true if the j^th friend request is successful or false if it is not.

Note: If u_j and v_j 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 <= 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

中文题目

给你一个整数 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

通过代码

高赞题解

拉到最下面还有44ms的超快版本喔！

这道题很明显是并查集，最简单的并查集题目是省份数量，这道题早先的名字叫“朋友圈”。

并查集的核心思想是“同属一个集合的节点拥有相同的根节点”，就像是一个圈子共同拥立一个头头。我们可以利用这个特性，让头头来管理整个圈子的“朋友名单”和“仇人名单”。

那么废话少说，先上代码~！

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

在并查集中，每个人都有一个“大哥”parent，

vector<int> parent = vector<int>(n, -1); // 开始时大家都没有大哥，记为-1

朋友圈里最大的大哥就是朋友圈的头头，我们可以通过root()函数递归找到最大的大哥。

// 头头没有大哥，或者他的大哥就是他自己
int root(int x) { return (parent[x] == -1 || parent[x] == x) ? x : root(parent[x]); };

在一个朋友圈里，所有人的头头都是同一个人。

所以我们可以让头头维护两个列表，一个是这个朋友圈所有人的名单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]);
}

接下来我们看对交友请求的for循环。

首先，对于每个交友请求requests[i]，先把两个圈子的头头x和y叫出来。

int x = root(requests[i][0]), y = root(requests[i][1]);

如果头头是同一个人，说明是同一个圈子。那么后面的操作也可以省略了。

if (x == y) continue;

谁的朋友多谁就是大哥，确保friends[x].size() >= friends[y].size()。
这是因为后面要遍历friends[y]，保证friends[y]的数量比friends[x]小可以提高速度。

if (friends[x].size() < friends[y].size()) swap(x, y);

在C++11中，[&]{ ... }()代表立即执行的匿名函数。在匿名函数内部return会直接跳到函数末尾，这样做是为了免去goto。

头头x首先检查y提交的朋友名单friends[y]，如果有一个people出现在x维护的仇人名单enemies[x]中，交朋友就失败了，立刻滚蛋。

for (auto people : friends[y]) {
    if (enemies[x].count(people) != 0) {
        result[i] = false;
        return;
    }
}

交朋友成功之后，头头x把y上交的仇人名单enemies[y]和朋友名单friends[y]添加到自己的对应名单里。

enemies[x].insert(enemies[y].begin(), enemies[y].end());
friends[x].insert(friends[y].begin(), friends[y].end());

然后y直接拜x为大哥，这样，y的朋友圈的所有人的头头就都变成了x。

parent[y] = x;

完成！

还可以更快！

由于n不会超过1000个，我们可以用bitset<1000>代替unordered_set<int>来减少内存占用，此时大量操作都可以简化为按位操作，速度更快！

class Solution {
    vector<int> parent;
    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) {
        parent = vector<int>(n, -1);
        vector<bitset<1000>> friends(n);
        for (int i = 0; i < n; i++) {
            friends[i][i] = true;
        }
        vector<bitset<1000>> enemies(n);
        for (auto& res : restrictions) {
            enemies[res[0]][res[1]] = true;
            enemies[res[1]][res[0]] = true;
        }  
        auto requests_size = requests.size();
        vector<bool> result(requests_size, true);
        for (int i = 0; i < requests_size; i++) {
            int x = root(requests[i][0]), y = root(requests[i][1]);
            if (x == y) continue;
            // 有没有哪个“y的朋友”同时又是“x的敌人”？
            if ((friends[y] & enemies[x]).any()) {
                result[i] = false;
				continue;
            }
            // 添加名单只需要按位或就可以了！
            enemies[x] |= enemies[y];
            friends[x] |= friends[y];
            parent[y] = x;
        }
        return result;
    }
};

统计信息

通过次数	提交次数	AC比率
2381	4849	49.1%

提交历史

提交时间	提交结果	执行时间	内存消耗	语言

凤起丶宛南

从来没有真正的绝境，只有心灵的迷途