| 10 | return x # 返回元素根节点的集合编号 |
| 11 | |
| 12 | def union(self, x, y): # 合并操作：令其中一个集合的树根节点指向另一个集合的树根节点 |
| 13 | root_x = self.find(x) |
| 14 | root_y = self.find(y) |
| 15 | if root_x == root_y: # x 和 y 的根节点集合编号相同，说明 x 和 y 已经同属于一个集合 |
| 16 | return False |
| 17 | |
| 18 | if self.rank[root_x] < self.rank[root_y]: # x 的根节点对应的树的深度 小于 y 的根节点对应的树的深度 |
| 19 | self.fa[root_x] = root_y # x 的根节点连接到 y 的根节点上，成为 y 的根节点的子节点 |
| 20 | elif self.rank[root_y] > self.rank[root_y]: # x 的根节点对应的树的深度 大于 y 的根节点对应的树的深度 |
| 21 | self.fa[root_y] = root_x # y 的根节点连接到 x 的根节点上，成为 x 的根节点的子节点 |
| 22 | else: # x 的根节点对应的树的深度 等于 y 的根节点对应的树的深度 |
| 23 | self.fa[root_x] = root_y # 向任意一方合并即可 |
| 24 | self.rank[root_y] += 1 # 因为层数相同，被合并的树必然层数会 +1 |
| 25 | return True |
| 26 | |
| 27 | def is_connected(self, x, y): # 查询操作：判断 x 和 y 是否同属于一个集合 |
| 28 | return self.find(x) == self.find(y) |