并查集

并查集是一种简洁而优雅的数据结构，主要用于解决一些元素分组的问题。它管理一系列不相交的集合，并支持两种操作：

• 合并（Union）：把两个不相交的集合合并为一个集合（建立连接）。
• 查询（Find）：查询两个元素是否在同一个集合中。

 ![image.png](https://cdn.nlark.com/yuque/0/2021/png/280095/1616379660784-2310d34f-bb87-41ff-a081-e573864d76a9.png#align=left&display=inline&height=241&margin=%5Bobject%20Object%5D&name=image.png&originHeight=481&originWidth=796&size=91077&status=done&style=none&width=398)

Union Quick版本

class UnionFind:
    """
        Quick Find
        id   0  1  2  3  4  5  6  7  8
        关系  4 5 有联系
        存储  0  1  2  3  5  5  6  7  8
        """
    def __init__(self, n: int):
        # 存储关系 初始值 - 当前数据只与本身有关系即存储所属集合的编号
        self.id = [i for i in range(n)]
        self.count = n
    #  获取集合数量
    def size(self):
        return self.count
    # 查找元素对应的集合编号
    def find(self, p: int) -> int:
        assert self.count > p >= 0, "p invalid"
        return self.id[p]
    # 是哦福存在连接 O(1)
    def is_connected(self, p: int, q: int) -> bool:
        return self.find(p) == self.find(q)
    # 合并元素p和元素q所对应的集合 O(n)
    def union(self, p: int, q: int):
        pid = self.find(p)
        qid = self.find(q)
        if pid == qid:
            return
        for i in range(self.count):
            # 如果元素id[i]所对应的集合id和p的相同,
            # 即找到了和p相关集合的值 和q建立关系
            if self.id[i] == pid:
                self.id[i] = qid

Quick Union

class UnionFind:
    """
    Quick Union
    id  0  1  2  3  4  5  6  7  8  9
    关系
        0    1         8
        ^    ^  ^      ^  ^
        |    |   \     |   \
        5    2   7     3   9
        ^              ^
        |              |
        6              4
    数组具体存储
        0  1  1  8  3  0  5  1  8  8
    问题 union(4 9) 节点层数太高
         9
         ^
         8
         ^
         |
         3
         ^
         4
         union(9 4)
         8
         ^  ^
         |   \
         3    9
         ^
         4
    find 指向共同的父节点即算是有关联
    """
    def __init__(self, n: int):
        self.id = [i for i in range(n)]
        self.count = n
    #  获取集合数量
    def size(self):
        return self.count
    #  时间复杂度O(h) h为树的高度
    def find(self, p: int) -> int:
        # 找不到则指向自己
        assert self.count > p >= 0, "p invalid"
        # 直到指向自己(即到根位置)
        while p != self.id[p]:
            # 表明已经指向其他根  从下往上查找根
            p = self.id[p]
        return p
    def is_connected(self, p: int, q: int) -> bool:
        return self.find(p) == self.find(q)
    def union(self, p: int, q: int):
        # 始终是 左指向右面的值
        p_root = self.find(p)
        q_root = self.find(q)
        if p_root == q_root:
            return
        # p元素的根指向变成q元素的根
        self.id[p_root] = q_root

基于Size（当前树的节点）优化

class UnionFind:
    """ 并差集优化 基于size的优化
        id     0  1  2  3  4  5  6  7  8  9
        size   1  1  1  1  1  1  1  1  1  1 (存储高度)
        第一步:
            模拟 union(4,3) -- p q
            4的根4 size 1
            3的根3 size 1
                   4
                   ^
                   |
                   3
            index     0  1  2  3  4  5  6  7  8  9
            id        0  1  2  4  4  5  6  7  8  9
            size      1  1  1  1  2  1  1  1  1  1
            模拟 union(3,8) -- p q
            3的根为4
            8的根为8
                   4  4   |       4
                   ^  ^   |  not  ^  ^
                   |  |   |       |   \
                   3  8   |       3    8
            index     0  1  2  3  4  5  6  7  8  9
            id        0  1  2  4  4  5  6  7  4  9
            size      1  1  1  1  3  1  1  1  1  1
        """
    def __init__(self, n: int):
        self.id = [i for i in range(n)]
        self.count = n
        self.size = [1 for _ in range(n)]  # size[i] 表示以i为根的集合中的元素个数
    #  获取集合数量
    def size(self):
        return self.count
    def find(self, p: int) -> int:
        # 找不到则指向自己
        assert self.count > p >= 0, "p invalid"
        while p != self.id[p]:
            p = self.id[p]
        return p
    def is_connected(self, p: int, q: int) -> bool:
        return self.find(p) == self.find(q)
    def union(self, p: int, q: int):
        p_root = self.find(p)
        q_root = self.find(q)
        if p_root == q_root:
            return
        # 判断当前父节点被关联的次数
        if self.size[p_root] < self.size[q_root]:
            self.id[p_root] = q_root
            self.size[q_root] = self.size[p_root]
        else:
            self.id[q_root] = p_root
            self.size[p_root] = self.size[q_root]

基于Rank（树的高度）

class UnionFind:
    """
    并查集优化 基于rank的优化  (树的高度)
    问题
          当前状态                 8
          -----------------> 7    ^
          |    |    |    |   |    |
          |    |    |    |   |    3
          |    |    |    |   |    ^
          |    |    |    |   |    |
          0    1    2    5   6    4
          按照UinonFind3操作 union(4,2)
          -----------------> 7
          |    |    |    |   |   \
          |    |    |    |   |     \
          0    1    2    5   6     8
                                   ^
                                   |
                                   3
                                   ^
                                   |
                                   4
          共 4 层
          优化方案
                               >   8
                              /    |
                             /     ^
          -----------------> 7     |
          |    |    |    |   |     3
          |    |    |    |   |     |
          0    1    2    5   6     4
          共 3 层
    """
    def __init__(self, n: int):
        self.id = [i for i in range(n)]
        self.count = n
        self.rank = [1 for _ in range(n)]  # rank[i] 表示以i为根的集合的高度
    #  获取集合数量
    def size(self):
        return self.count
    def find(self, p: int) -> int:
        # 找不到则指向自己
        assert self.count > p >= 0, "p invalid"
        while p != self.id[p]:
            p = self.id[p]
        return p
    def is_connected(self, p: int, q: int) -> bool:
        return self.find(p) == self.find(q)
    def union(self, p: int, q: int):
        p_root = self.find(p)
        q_root = self.find(q)
        if p_root == q_root:
            return
        # 判断当前父节点的高度
        if self.rank[p_root] < self.rank[q_root]:
            self.id[p_root] = q_root
        elif self.rank[q_root] < self.rank[p_root]:
            self.id[q_root] = p_root
        else:
            self.id[q_root] = p_root
            self.rank[p_root] += 1

路径压缩

class UnionFind:
    """
    并查集优化 路径压缩
    问题
          当前状态
                1
               /
              2
             /
            3
           /
          5
         /
        9
        在查找过程中进行路径压缩
        step 1
                1
               /
              2
             /
            3
           / \
          5   9
        step 2
                1
               /  \
              2    3
                  / \
                 5   9
    """
    def __init__(self, n: int):
        self.id = [i for i in range(n)]
        self.count = n
        self.rank = [1 for _ in range(n)]  # rank[i] 表示以i为根的集合的高度
    #  获取集合数量
    def size(self):
        return self.count
    def find(self, p: int) -> int:
        # 找不到则指向自己
        assert self.count > p >= 0, "p invalid"
        while p != self.id[p]:
            self.id[p] = self.id[self.id[p]]
            p = self.id[p]
        return p
    def is_connected(self, p: int, q: int) -> bool:
        return self.find(p) == self.find(q)
    def union(self, p: int, q: int):
        p_root = self.find(p)
        q_root = self.find(q)
        if p_root == q_root:
            return
        # 判断当前父节点的高度
        if self.rank[p_root] < self.rank[q_root]:
            self.id[p_root] = q_root
        elif self.rank[q_root] < self.rank[p_root]:
            self.id[q_root] = p_root
        else:
            self.id[q_root] = p_root
            self.rank[p_root] += 1

路径压缩2

class UnionFind:
    """
    并查集优化 路径压缩
    问题
          当前状态
                1
               /
              2
             /
            3
           /
          5
         /
        9
        在查找过程中进行路径压缩
        step 2
                1
              /||\
            / / | \
          2  3  5  9
    """
    def __init__(self, n: int):
        self.id = [i for i in range(n)]
        self.count = n
        self.rank = [1 for _ in range(n)]  # rank[i] 表示以i为根的集合的高度
    #  获取集合数量
    def size(self):
        return self.count
    def find(self, p: int) -> int:
        # 找不到则指向自己
        assert self.count > p >= 0, "p invalid"
        if p != self.id[p]:
            self.id[p] = self.find(self.id[p])
        return self.id[p]
    def is_connected(self, p: int, q: int) -> bool:
        return self.find(p) == self.find(q)
    def union(self, p: int, q: int):
        p_root = self.find(p)
        q_root = self.find(q)
        if p_root == q_root:
            return
        # 判断当前父节点的高度
        if self.rank[p_root] < self.rank[q_root]:
            self.id[p_root] = q_root
        elif self.rank[q_root] < self.rank[p_root]:
            self.id[q_root] = p_root
        else:
            self.id[q_root] = p_root
            self.rank[p_root] += 1