代码随想录算法训练营第五十五天 | 并查集理论基础、107. 寻找存在的路径

一、并查集理论基础

文章链接：并查集理论基础 | 代码随想录 (programmercarl.com)

功能

1. 将两个元素添加到一个集合中。
2. 判断两个元素是否在同一个集合中。

代码模板

"""
并查集 路径压缩 模板
"""
class UnionFindSet:
    def __init__(self, size):
        self.parent = list(range(size))                         # 初始化并查集数组
    
    # 并查集的寻根过程
    def find(self, u):
        if self.parent[u] != u:                                 # 如果 u 不是根节点
            self.parent[u] = self.find(self.parent[u])          # 路径压缩
        return self.parent[u]

        # # 下面为展开版
        # if self.parent[u] == u:
        #     return u
        # else:
        #     return self.parent[u] = self.find[self.parent[u]]   # 路径压缩
         
    # 判断 u 和 v 是否找到同一个根，是个 bool 类型
    def isSame(self, u, v):
        u = self.find(u)
        v = self.find(v)
        return u == v
    
    # 将 u -> v 这条边加入并查集
    def join(self, u, v):
        root_u = self.find(u)                                   # 寻找 u 的根
        root_v = self.find(v)                                   # 寻找 v 的根

        # 如果发现根不同，将 v 的根指向 u 的根
        if root_u != root_v:
            self.parent[root_v] = root_u

并查集总共可以实现三个功能：

1. find(self, u) 函数，寻找根节点，即判断该节点的祖先节点是哪个；
2. isSame(self, u, v) 函数，判断两个节点是否在同一个根；
3. join(self, u, v) 函数，将两个节点接入同一个集合，即连在同一根节点上。

Note：join 函数一定要先通过 find 函数寻根，在进行关联。

扩展：按秩(rank)合并

准则：秩小的树合入到秩大的树，这样可以保证最后合并的树的秩最小，降低在树上查找路径的长度。

"""
并查集 按秩(rank)合并 代码模板
rank 表示树的高度，即树中结点层次的最大值
"""
class UnionFindSet:
    def __init__(self, size):
        self.parent = list(range(size))             # 初始化父节点数组
        self.rank = [1] * size                      # 初始化每棵树的高度为 1

    def init(self):
        for i in range(len(self.parent)):
            self.parent[i] = i                      # 将每个节点的父节点初始化为自身
            self.rank[i] = 1                        # 可以选择不写这一行

    def find(self, u):
        if self.parent[u] != u:
            return self.find(self.parent[u])        # 不进行路径压缩
        return u

    def is_same(self, u, v):
        return self.find(u) == self.find(v)

    def join(self, u, v):
        root_u = self.find(u)                       # 寻找 u 的根
        root_v = self.find(v)                       # 寻找 v 的根

        if self.rank[root_u] <= self.rank[root_v]:
            self.parent[root_u] = root_v            # rank 小的树合并到 rank 大的树
        else:
            self.parent[root_v] = root_u
        
        # 如果两棵树高度相同，将 v 的高度 +1
        if self.rank[root_u] == self.rank[root_v] and root_u != root_v:
            self.rank[root_v] += 1  

Note：无需做路径压缩，一旦做路径压缩，记录的高度不准确了。了解即可，还是常用路径压缩。

二、107. 寻找存在的路径

题目连接：107. 寻找存在的路径 (kamacoder.com)
文章讲解：代码随想录 (programmercarl.com)——107. 寻找存在的路径

思路：判断是否有一条从节点 source 出发到节点 destination 的路径存在就是判断这两条节点是否在同一个集合中。使用 join 将每条边加入到并查集，最后用 isSame 判断是否属于同一个根即可。

class UnionFindSet:
    def __init__(self, n):
        # n + 1 是因为节点编号从1 到 n
        self.parent = list(range(n + 1))
        
    def find(self, u):
        if self.parent[u] != u:
            self.parent[u] = self.find(self.parent[u])
        return self.parent[u]
        
    def isSame(self, u, v):
        u = self.find(u)
        v = self.find(v)
        return u == v
        
    def join(self, u, v):
        root_u = self.find(u)
        root_v = self.find(v)
        
        if root_u != root_v:
            self.parent[root_v] = root_u
            

if __name__ == '__main__':
    n, m = map(int, input().split())                    # 读取节点数和边数
    
    ufs = UnionFindSet(n)                               # 创建并查集实例
    
    for _ in range(m):
        s, t = map(int, input().split())                # 读取边
        ufs.join(s, t)                                  # 将边加入并查集中
        
    source, destination = map(int, input().split())     # 读取源节点和目标节点
    
    if ufs.isSame(source, destination):
        print(1)
    else:
        print(0)