什么是并查集？
这里借用百度百科的一句话：并查集是一种树型的数据结构，用于处理一些不相交集合（disjoint sets）的合并及查询问题。常常在使用中以森林来表示。假设现在有一个武林大会，包含了少林、峨嵋、武当等门派，通过并查集就可以将每个人归类到自己的门派中。
代码实现
代码语言：javascript复制class UnionFind:
def __init__(self):
self.co = 0 # 用于记录群的个数
self.parent = [] # 索引是每个节点本身，值是每个节点的父节点
self.size = [] # 用于记录每个群的节点数目
#
def find(self, x):
while self.parent[x] != x:
# self.parent[x] = self.parent[self.parent[x]] # 用于路径压缩
x = self.parent[x]
return x
def union(self, p, q):
rootP = self.find(p)
rootQ = self.find(q)
if rootP == rootQ:
return
# 下面的这个if语句用将节点数少的合并到节点数多的群中
if self.size[rootP] > self.size[rootQ]:
self.parent[rootQ] = rootP
self.size[rootP] = self.size[rootQ]
else:
self.parent[rootP] = rootQ
self.size[rootQ] = self.size[rootP]
self.co -= 1
# 用于判断p和q之间是否连通，如果两个节点的父节点是相同的，那么就是连通的
def connected(self, p, q):
rootP = self.find(p)
rootQ = self.find(q)
return rootP == rootQ
# 返回有多少个群
def count(self):
return self.co
# 初始化，节点的父节点就是其本身，假设n=10，那么就有10个群，self.parent=[0,1,2,3,4,5,6,7,8,9]，self.parent[0]=0表示0节点的父节点是0。每个群的size，也就是包含的节点数目就是1，self.size[0]=1。
def uf(self, n):
self.co = n
self.parent = [0 for _ in range(n)]
self.size = [0 for _ in range(n)]
for i in range(n):
self.parent[i] = i
self.size[i] = 1
unionF = UnionFind()
unionF.uf(10)
print("初始化每个节点的父节点：", unionF.parent)
print("初始化的群个数：", unionF.count())
unionF.union(0, 3) # 0,3建立关系
unionF.union(3, 7) # 3,7建立关系
unionF.union(7, 9) # 7,9建立关系
unionF.union(2, 8) # 2,8建立关系
print("判断{}与{}之间是否在一个群里面：{}".format(3, 8, unionF.connected(3, 8)))
print("返回节点{}的父节点{}".format(7, unionF.find(7)))
print("当前每个节点的父节点：", unionF.parent)
print("当前群的个数：", unionF.count())
print("当前每一个群的节点个数：", unionF.size)结果：
初始化每个节点的父节点： [0, 1, 2, 3, 4, 5, 6, 7, 8, 9] 初始化的群个数： 10 判断3与8之间是否在一个群里面：False 返回节点7的父节点3 当前每个节点的父节点： [3, 1, 8, 3, 4, 5, 6, 3, 8, 3] 当前群的个数： 6 当前每一个群的节点个数： [1, 1, 1, 4, 1, 1, 1, 1, 2, 1]
更具体的介绍可以去参考labuladong的算法小抄。
