我正在684. Redundant Connection部分成功地解決來自 Leetcode 的問題（我沒有通過其中一個測驗用例）。問題如下：
在這個問題中，樹是一個無向圖，它是連通的并且沒有環。
您將得到一個圖，該圖以一棵樹的形式開始，其中 n 個節點從 1 到 n 標記，并添加了一條附加邊。添加的邊有兩個從 1 到 n 中選擇的不同頂點，并且不是已經存在的邊。該圖表示為長度為 n 的陣列邊，其中邊[i] = [ai, bi] 表示圖中的節點 ai 和 bi 之間存在一條邊。
回傳可以洗掉的邊，以便生成的圖是 n 個節點的樹。如果有多個答案，則回傳輸入中最后出現的答案。
我使用 BFS 解決了這個問題，它給出了 O(n^2) 的時間復雜度，但是我讀到使用 union-find 會給出 O(n) 的時間復雜度。我嘗試使用 union-find path 壓縮只是部分起作用，我一直在弄清楚為什么。
對于以下這些資料，我的代碼作業正常（意味著我的代碼回傳正確的邊緣）：
但是，對于下面的這個測驗用例，我的代碼沒有成功找到正確的邊（我的 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
}
}
關于問題可能是什么的任何建議？我一直無法弄清楚。
uj5u.com熱心網友回復：
var parent = parents[node]
while(parents[node] != parent){
你永遠不會進入 while 回圈。
轉載請註明出處，本文鏈接：https://www.uj5u.com/qiye/510109.html
標籤：算法科特林数据结构