在部分工作的无向树中查找冗余边的代码

Question

我正在解决来自Leetcode的684. Redundant Connection问题，并取得了部分成功(我失败了一个测试案例)。现提出以下问题：

在这个问题中，树是一个无向图，它是连通的，没有循环。

给出了一个从1到n标记为n个节点的树开始的图，并添加了一个额外的边。所增加的边有两个从1到n的不同顶点，而不是一个已经存在的边。图表示为长度为n的数组边，其中edgesi = ai，bi表示图中的节点ai和bi之间有一条边。

返回可以删除的边，以便生成的图是n个节点的树。如果有多个答案，则返回输入中最后出现的答案。

我用BFS解决了这个问题，它的时间复杂度为O(n^2)，但是我读到使用union会给出O(n)的时间复杂度。我尝试使用联合-查找+路径压缩只是部分工作，我被困在弄清楚原因。

对于以下数据，我的代码工作正常(意味着我的代码返回正确的边缘)：

​

​

但是，对于下面这个测试用例，我的代码没有成功地找到正确的边缘(我的union-find遍历所有边缘并返回false，这意味着没有多余的边)：

输入数据：[[7,8],[2,6],[2,8],[1,4],[9,10],[1,7],[3,9],[6,9],[3,5],[3,10]]

​

​

从日志中，我可以看到，我的union-find构造了如下图(没有检测到的冗余边)：

​

​

这是我的代码：

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
}

}

，关于这个问题可能是什么，有什么建议吗？，我还没能弄清楚。

Answer 1

var parent = parents[node]
while(parents[node] != parent){

你永远不会进入时间循环。