LeetCode 684冗余连接：Union-Find实现部分测试用例失效求助

题目描述 #

本题中，树是指连通且无环的无向图。
给定一个初始为n个节点（编号1到n）的树，添加了一条额外的边。添加的边连接两个不同的节点，且原本不存在于树中。图以长度为n的edges数组表示，其中edges[i] = [ai, bi]表示节点ai和bi之间存在一条边。
返回一条可以移除的边，使得移除后剩余的图是n个节点的树。若有多个答案，返回输入中最后出现的边。

问题场景 #

使用BFS解法可通过测试但时间复杂度为O(n²)，改用带路径压缩和按秩合并的并查集方案后，大部分测试用例正常，但针对输入[[7,8],[2,6],[2,8],[1,4],[9,10],[1,7],[3,9],[6,9],[3,5],[3,10]]，代码遍历所有边后未检测到冗余边，最终返回空数组。

原代码 #

class Solution {
fun findRedundantConnection(edges: Array<IntArray>): IntArray {
    
val parents = IntArray(edges.size + 1) // 1 to N, we dont use 0
for(i in 1..parents.size - 1)
    parents[i] = i //each node is its own parent, since this is a undirected graph
val rank = IntArray(edges.size + 1){ 1 } //all nodes have rank 1 since they are their own parent
val res = IntArray(2)

for(edge in edges){
    val (node1, node2) = edge
    if(union(node1,node2, parents, rank, res) == false)
        return intArrayOf(node1, node2)
}
    
return res
}

private fun find(
    node: Int, 
    parents: IntArray
): Int{
    var parent = parents[node]
    while(parents[node] != parent){
        parents[parent] = parents[parents[parent]] //path compression
        parent = parents[parent]
    }
    return parent
}

//modified union which return false on redundant connection
private fun union(
    node1: Int, 
    node2: Int, 
    parents: IntArray, 
    rank: IntArray, 
    res: IntArray
): Boolean{
    val parent1 = find(node1, parents)
    val parent2 = find(node2, parents)
    if(parent1 == parent2){ //redundant connection
        res[0] = node1
        res[1] = node2
        return false
    } 
    if(rank[parent1] > rank[parent2]){
        parents[parent2] = parent1
        rank[parent1] += rank[parent2]
    }else{ // rank[parent1] <= rank[parent2]
        parents[parent1] = parent2
        rank[parent2] += rank[parent1]
    }
    return true
}
}

问题原因 #

核心错误出在find函数的逻辑实现，导致无法正确定位节点的根父节点：

• 原find函数的循环条件parents[node] != parent完全错误：node是传入的固定初始节点，parent初始值为parents[node]，此时两者完全相等，循环体根本不会执行，直接返回当前节点的直接父节点，而非整个连通分量的根节点。
• 这种情况下，union函数无法正确判断两个节点是否属于同一集合，即使节点在同一个连通分量中，也会被误判为不同集合进行合并，最终无法检测到环的存在。

修正后的find函数 #

迭代版（带完整路径压缩） #

private fun find(node: Int, parents: IntArray): Int {
    var current = node
    // 先找到根节点
    while (parents[current] != current) {
        current = parents[current]
    }
    // 路径压缩：将路径上所有节点直接指向根，加速后续查询
    var temp = node
    while (parents[temp] != current) {
        val nextParent = parents[temp]
        parents[temp] = current
        temp = nextParent
    }
    return current
}

简洁迭代版（路径压缩） #

private fun find(node: Int, parents: IntArray): Int {
    var current = node
    while (parents[current] != current) {
        // 路径压缩：将当前节点的父节点指向祖父节点，缩短路径
        parents[current] = parents[parents[current]]
        current = parents[current]
    }
    return current
}

内容的提问来源于stack exchange，提问作者CJR