并查集及Python实现

并查集：在计算机科学中，并查集是一种树型的数据结构，用于处理一些不交集（Disjoint Sets）的合并及查询问题。 —wiki

定义

​ 并查集，顾名思义，包含了合并和查询操作，用于解决动态连通性问题。

实现过程

# 主体框架
class UnionFind(object):

    # 初始化
    def __init__(self):
        pass

    # 查询根节点
    def find(self):
        pass

    # 合并节点
    def union(self):
        pass

    # 判断两个节点是否连通
    def is_same_set(self):
        pass

• 初始化

  将所有节点的父节点设为None

  def __init__(self, M):
      self.father_dict = {}
  
      # 记录集合的数量，一般为返回值
      self.nums_set = 0
  
      for i in range(len(M)):
          if i not in self.father_dict:
              self.father_dict[i] = None
              # 集合的数量+1
              self.nums_set += 1

• 查询

  def find(self, x):
      root = x
      while self.father_dict[root] != None:
          root = self.father_dict[root]
  
      # 路径压缩
      while x != root:
          cur_father = self.father_dict[x]
          self.father_dict[x] = root
          x = cur_father
      return root

• 合并

  def union(self, a, b):
      a_root, b_root = self.find(a), self.find(b)
  
      # 任意指定一个节点为父节点
      if a_root != b_root:
          self.father_dict[a_root] = b_root
          self.nums_set -= 1

• 判断是否在同一集合

  def is_same_set(self, a, b):
      return self.find(a) == self.find(b)