a problem with code

[zhangbo2008]

LeetCode-Go/template/UnionFind.go

Line 104 in f0792d1

if proot == len(uf.parent)-1 {

感觉这个地方应该是:

应该是 uf.count[proot]== len(uf.parent)-1

[hekai000]

对，这里有问题，应该是：
if uf.count[proot ] == len(uf.parent)-1 {
//proot is the root of the tree, no need to merge
} else if uf.count[qroot] == len(uf.parent)-1 {
proot , qroot = qroot, proot
} else if uf.count[qroot] > uf.count[proot] {
proot , qroot = qroot, proot
}

[haowan1015]

呵呵，来信收到，谢谢

[xiaokuer]

这是来自QQ邮箱的假期自动回复邮件。   您好，我最近正在休假中，无法亲自回复您的邮件。我将在假期结束后，尽快给您回复。

[halfrost]

@zhangbo2008 我这里的 proot 和 qroot 只是代表 index，存的 count 是在 uf.count[proot] 中。

[halfrost]

To settle this: proot / qroot are node indices (the roots returned by Find), while component sizes are stored separately in uf.count[...].

So proot == len(uf.parent)-1 asks "is p's root the node at the last index?". In this UnionFindCount variant the last index is a designated virtual super-root (e.g. the "roof" node in 803. Bricks Falling When Hit) that everything must attach to, so it is kept as the parent and never made a child. Replacing it with uf.count[proot] == len(uf.parent)-1 would compare a component size against an index, which is not equivalent and would be incorrect.

This template is used by 803 / 924 / 952 and all of their tests pass. Closing as working-as-intended — thanks for the careful read.