数据结构之并查集
并查集是一种用于管理元素所属集合的数据结构，实现为一个森林，其中每棵树表示一个集合，树中的节点表示对应集合中的元素。用于解决图的连通性问题，即给定一个无向图，要求判断某两个元素之间是否存在相连的路径（连通）。
并查集支持两种操作：
- 合并（Union）：合并两个元素所属集合（合并对应的树）
- 查询（Find）：查询某个元素所属集合（查询对应的树的根节点），这可以用于判断两个元素是否属于同一集合
1class UF:
2 """
3 self.id 存当前id的祖宗节点
4 self.size 当节点是祖宗节点时有效。每个节点都是其自身的祖宗（默认为1）
5 """
6 def __init__(self, n):
7 self.id = list(range(n)) # 初始化每个节点都是其自身的祖宗
8 self.size = [1] * n
9
10 def find(self, p):
11 if (self.id[p] == p):
12 return p
13 self.id[p] = find(self.id[p])
14 return self.id[p]
15
16 def union(self, p, q):
17 p_root = self.find(p)
18 q_root = self.find(q)
19
20 if (p_root != q_root) {
21 if(self.size[p_root] < self.size[q_root]) { # qRoot是祖宗节点
22 self.id[p_root] = self.id[q_root];
23 self.size[q_root] += self.size[p_root]; # 祖宗节点的 size +=
24 }else {
25 self.id[q_root] = self.id[p_root]; # pRoot是祖宗节点
26 self.size[p_root] += self.size[q_root]; # 祖宗节点的 size +=
27 }
28 }
本文的版权归作者 longfellow 所有，采用 The MIT License (MIT)。任何人可以进行转载、分享，但不可在未经允许的情况下用于商业用途；转载请注明出处。感谢配合！