wrc's Wiki

更改

Union find (查看源代码)

2021年10月10日 (日) 19:39的版本

添加366字节 、 2021年10月10日 (日) 19:39
无编辑摘要
第1行： 第1行：  
[[Category:刷题]]
 
[[Category:刷题]]
 
并查集：用于处理一些不交集（Disjoint sets）的合并及查询问题。
 
并查集：用于处理一些不交集（Disjoint sets）的合并及查询问题。
 +
 +
在求最小生成树的 [[wikipedia:Kruskal's_algorithm|Kruskal 算法]] 中就用到了并查集。
    
== 算法 ==
 
== 算法 ==
第13行： 第15行：     
<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
第23行： 第25行：  
=== 合并 ===
 
=== 合并 ===
   −
{{TODO|union}}
+
如果两个节点的代表不同，则将它们的代表相连。注意最后一行中是对两节点的代表（ri 和 rj）进行操作，而不是 i 和 j。
 +
<syntaxhighlight lang=python>
 +
ri = find_repr(i)
 +
rj = find_repr(j)
 +
if ri != rj:
 +
    representative[ri] = rj
 +
</syntaxhighlight>
    
== 相关题目 ==
 
== 相关题目 ==
取自“https://wiki.ruo-chen.wang/wiki/特殊:移动版差异/448”