Code for finding redundant edges in a undirected tree partially working-CodePudding

I am solving the question 684. Redundant Connection from from Leetcode with partial success (I am failing one of the testcases). The question is asked as following:

In this problem, a tree is an undirected graph that is connected and has no cycles.

You are given a graph that started as a tree with n nodes labeled from 1 to n, with one additional edge added. The added edge has two different vertices chosen from 1 to n, and was not an edge that already existed. The graph is represented as an array edges of length n where edges[i] = [ai, bi] indicates that there is an edge between nodes ai and bi in the graph.

Return an edge that can be removed so that the resulting graph is a tree of n nodes. If there are multiple answers, return the answer that occurs last in the input.

I solved this using BFS which gives a time complexity of O(n^2), however I read that using union-find will give a time complexity of O(n). My try with using union-find path compression is only partially working, and I am stuck figuring out why.

For these following data, my code is working correctly (Meaning my code returns correct edge):

However, for this testcase below, my code don't succeed in finding the correct edge (My union-find runs through all the edges and return false, meaning there was no redundant edges):

Input data: [[7,8],[2,6],[2,8],[1,4],[9,10],[1,7],[3,9],[6,9],[3,5],[3,10]]

From logs i can see that my union-find constructs the graph as following (with no detected redundant edges):

Here is my code:

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
}

}

Any suggestions on what the problem might be? I have not been able to figure it out.

CodePudding user response：

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

You're never going to get into the while loop.