528
个编辑
更改
跳到导航
跳到搜索
第10行：
第10行： − representatives = [i for i in range(n)]+ 第19行：
第19行： − + − + − + 第34行：
第34行： − representative[ri] = rj +
→算法
新添加一个元素时，它的 parent 是它自己。特别地，初始化 union find 时可用
新添加一个元素时，它的 parent 是它自己。特别地，初始化 union find 时可用
<syntaxhighlight lang=python>
<syntaxhighlight lang=python>
repres = [i for i in range(n)]
</syntaxhighlight>
</syntaxhighlight>
<syntaxhighlight lang=python>
<syntaxhighlight lang=python>
def find_repr(x):
def find_repr(x):
if x.parent == x:
if repres[x] == x:
return x
return x
else:
else:
x.parent = find_representative(x.parent)
repres[x] = find_repre(repres[x])
return x.parent
return repres[x]
</syntaxhighlight>
</syntaxhighlight>
rj = find_repr(j)
rj = find_repr(j)
if ri != rj:
if ri != rj:
repres[ri] = rj
</syntaxhighlight>
</syntaxhighlight>