并查集及Python实现

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

定义

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

实现过程

 1# 主体框架
 2class UnionFind(object):
 3
 4    # 初始化
 5    def __init__(self):
 6        pass
 7
 8    # 查询根节点
 9    def find(self):
10        pass
11
12    # 合并节点
13    def union(self):
14        pass
15
16    # 判断两个节点是否连通
17    def is_same_set(self):
18        pass

• 初始化

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

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

• 查询

   1def find(self, x):
   2	root = x
   3    while self.father_dict[root] != None:
   4        root = self.father_dict[root]
   5
   6    # 路径压缩
   7    while x != root:
   8        cur_father = self.father_dict[x]
   9        self.father_dict[x] = root
  10        x = cur_father
  11    return root
  

• 合并

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

• 判断是否在同一集合

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