528
个编辑
更改
跳到导航
跳到搜索
第1行：
第1行： + + 第13行：
第15行： − + 第23行：
第25行： − {{TODO|union}}+ + + + + + +
无编辑摘要
[[Category:刷题]]
[[Category:刷题]]
并查集：用于处理一些不交集（Disjoint sets）的合并及查询问题。
并查集：用于处理一些不交集（Disjoint sets）的合并及查询问题。
在求最小生成树的 [[wikipedia:Kruskal's_algorithm|Kruskal 算法]] 中就用到了并查集。
== 算法 ==
== 算法 ==
<syntaxhighlight lang=python>
<syntaxhighlight lang=python>
def find_representative(x):
def find_repr(x):
if x.parent == x:
if x.parent == x:
return x
return x
=== 合并 ===
=== 合并 ===
如果两个节点的代表不同，则将它们的代表相连。注意最后一行中是对两节点的代表（ri 和 rj）进行操作，而不是 i 和 j。
<syntaxhighlight lang=python>
ri = find_repr(i)
rj = find_repr(j)
if ri != rj:
representative[ri] = rj
</syntaxhighlight>
== 相关题目 ==
== 相关题目 ==