错误在于 findRoot 函数.您当前正在检查所提供的节点( id )是否为其自身的父级，即为其集合的代表元素.如果不是，则假定其父代为代表，然后将其返回.但这不一定是正确的，即使您正在使用路径压缩.

The error lies in the findRoot function. You're currently checking if the node supplied (id) is the parent of itself, i.e., is the representative element of its set. If it isn't, you assume that its parent is the representative, and return it. But that isn't necessarily true, even if you're using path compression.

假设您有4个节点A，B，C和D.边为:A-> B，B-> C，A-> D.

Say you have 4 nodes A, B, C, and D. Edges are: A -> B, B -> C, A -> D.

您首先将A的父级设置为B，然后将B的父级设置为C.到这里都可以.但是，当您处理最后一条边时，请调用 findRoot(...，A).它检查A是否不是其自身的父级，然后返回其父级B.但是，A集合的代表元素甚至不是B，而是C.您可以看到B也不是其自身的父级.组件数量在这里并没有弄乱，但是您可以看到它如何产生错误的结果.

You first set A's parent to be B, then B's parent to be C. It's fine till here. But when you arrive at processing the last edge, you call findRoot(..., A). It checks that A isn't its own parent, and so returns its parent B. But, the representative element of A's set isn't even B, it's C. You can see that B isn't its own parent as well. The component count doesn't mess up here, but you can see how it can produce wrong results.

唯一需要做的更改是您必须继续寻找代表元素，而不仅仅是经过1次检查后返回.

The only change needed is that you have to keep looking for the representative element, and not just return after 1 check.

您的新方法将遵循以下原则:

Your new method will be along the lines of:

def findRoot(self, roots, id):
    oid=id
    while roots[id] != id: # Keep looking for the representative
        id=roots[id]

    roots[oid]=id
    return id

此更改导致对输入数据中的6个连接组件进行计数.通过DFS确认.

This change results in counting 6 connected components in your input data. Confirmed with DFS.

要实现路径压缩，请将在此循环中遇到的每个节点的父节点设置为最终值.

To implement path compression, set the parent of each of the nodes you encountered in this loop to the final value.