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

https://leetcode-cn.com/problems/process-restricted-friend-requests/

一、并查集

class UnionFind:
    # 构造函数传入totalNodes为总节点数
    def __init__(self, totalNodes):
        # parents[i]表示i的根，初始i的根为其自身
        self.parents = [i for i in range(totalNodes)]
        # 连通分量数
        self.count = totalNodes
        # 连通分量大小，即树的“重量”
        self.size = [1] * totalNodes
    # 合并连通区域是通过find来操作的, 即看这两个节点是不是在一个连通区域内.
    def union(self, node1, node2):
        root1 = self.find(node1)
        root2 = self.find(node2)
        # 不连通才合并
        if root1 != root2:
              # 小树合并到大树
            if self.size[root1] > self.size[root2]:
                self.parents[root2] = root1
                self.size[root1] += self.size[root2]
            else:
                self.parents[root1] = root2
                self.size[root2] += self.size[root1]
            # 连通分量数减一
            self.count -= 1

    # 查找最终的根
    def find(self, node):
        while self.parents[node] != node:
            self.parents[node] = self.parents[self.parents[node]]
            node = self.parents[node]
        return node

    # 判断两个点是否连通
    def isConnected(self, node1, node2):
        return self.find(node1) == self.find(node2)

    # 返回连通分量个数
    def count(self):
        return self.count
    

算法：每轮将前i个（i从0到n-1）好友请求（设为[a,b]）写入并查集，即把a，b连通。然后用限制集中的每个限制关系c、d进行测试，若c与d连通，说明这i个请求不能成立（确切的说是第i个）

class Solution:
    def friendRequests(self, n: int, restrictions: List[List[int]], requests: List[List[int]]) -> List[bool]:
        res = []
        passIndex = set()		#标记不能成立的请求
        for i in range(len(requests)):
            uf = UnionFind(n)	#每轮创建一个并查集
            for j in range(i+1):
                if j in passIndex:	#若该请求被标记不能成立，则跳过
                    continue
                a, b = requests[j][0], requests[j][1]
                uf.union(a,b)
            flag = True
            for c, d in restrictions:	#测试所有限制条件
                if uf.isConnected(c, d):
                    flag = False
                    passIndex.add(i)
                    break
            res.append(flag)
        return res 

优化

每个集合内都是直接朋友或者间接朋友。

对于：x = requests[i][0], y = requests[i] 如果x所处的集合与y所处的集合相等，这样就意味着x和y已经是朋友了 如果x所处的集合与y所处的集合不等，需要判断x所处的集合与y所处的集合能否合并，可以遍历restrictions，具体如下：

对于：p = restrictions[j][0], q = restrictions[j][1]有以下两种情况不合符条件 如果x与p在同一个集合 且 q与y在同一个集合 如果y与p在同一个集合 且 x与q在同一个集合 上面两种情况都说明，若x与y成为朋友，则p和q成为间接朋友，这是限制条件不允许的

# 并查集模板略
class Solution:
    def friendRequests(self, n: int, restrictions: List[List[int]], requests: List[List[int]]) -> List[bool]:
        res = []
        uf = UnionFind(n)
        for x, y in requests:
            flag = True
            if not uf.isConnected(x, y):
                for p, q in restrictions:
                    if uf.isConnected(p, x) and uf.isConnected(q, y) or uf.isConnected(q, x) and uf.isConnected(p, y):
                        flag = False
                        break
            if flag:
                uf.union(x, y)
            res.append(flag)
        return res