→ ken52011219: 做完第二個for 迴圈就不變了 01/23 16:22
→ ken52011219: 我做的答案是回傳為x2 01/23 16:23
→ ken52011219: 我是看不太懂它答案在寫甚麼啦@@ return 1有點答非 01/23 16:27
→ ken52011219: 所問 01/23 16:27
→ yupog2003: 我是畫這樣，箭頭指的方向是parent，有用union by rank 01/23 16:27
→ yupog2003: 和path compression，但我沒有答案也不知道這樣對不對 01/23 16:27
→ yupog2003: 原來All x are in the same set，那我鐵定畫錯，先不要 01/23 16:29
→ yupog2003: 理我的圖 01/23 16:29
→ yupog2003: 喔不我看到其實有改題目了，Union(x1,x5)被改成 01/23 16:30
→ yupog2003: Union(x1,x15)，那好像有一點點機會是對的XD 01/23 16:30
→ ken52011219: 感覺是沒差QQ 我是憑印象照著union的code走 01/23 16:31
→ ken52011219: 做到第二個迴圈結束就不會有任何相異了 01/23 16:32
→ yupog2003: 第二個for loop的union是Union(x1,x2),Union(x3,x4), 01/23 16:35
→ yupog2003: Union(x5,x6),...,Union(x15,x16)嗎？ 01/23 16:35
→ yupog2003: 還是我誤會了什麼... 01/23 16:35
→ AkariAkaza: 我畫出來跟yu的差不多，不過x10是在x9那串 01/23 16:38
→ ken52011219: 是 X1,X2 X2,X3 ...下去 01/23 16:39
→ yupog2003: 我x10是在Union(x1,x10)的時候因為會先find(x10)，因此 01/23 16:41
→ yupog2003: 根據path compression會把x10的parent指向root 01/23 16:41
→ AkariAkaza: by2 by4是什麼意思？ 01/23 16:41
→ yupog2003: 不過Union by rank應該是rank大當root，我搞成小的了 01/23 16:42
→ yupog2003: 我覺得應該是i一次+2 or +4拉...第一次看到這種寫法 01/23 16:42
→ AkariAkaza: union by rank 我是當成高度來看 01/23 16:45
→ ken52011219: 題目沒說要 union by rank 01/23 16:53
→ ken52011219: 剛剛po的解答無誤，我畫錯了 QQ 01/23 16:53
→ ken52011219: 等等 我理解錯誤 我再想一下@_@ 01/23 16:55
→ ken52011219: 答案讓我可以接受XDD 01/23 17:00
→ ken52011219: 看有沒有人有其他的看法 01/23 17:01
→ AkariAkaza: 大標題有寫 01/23 17:20
→ ken52011219: 哦哦 我看到了! 原本只看原po的圖而已 01/23 17:23
→ ken52011219: 不多 01/23 17:30
→ ken52011219: 抱歉 應該是yupog大說的 Orz +2 +4 沒錯 01/23 17:35
→ yupog2003: 再畫一次用rank大的當root的，這樣才跟simulation跑出 01/23 17:50
→ yupog2003: 來的一樣，我剛剛那個教授應該會直接打錯... 01/23 17:51
→ AkariAkaza: The first way, called譃nion by rank, is to always 01/23 17:55
→ AkariAkaza: attach the smaller tree to the root of the larger 01/23 17:55
→ AkariAkaza: tree. Since it is the depth of the tree that affec 01/23 17:56
→ AkariAkaza: ts the running time, the tree with smaller depth g 01/23 17:56
→ AkariAkaza: ets added under the root of the deeper tree, which 01/23 17:56
→ AkariAkaza: only increases the depth if the depths were equal 01/23 17:56
→ AkariAkaza: . 01/23 17:56
→ AkariAkaza: wiki 上的說法 01/23 17:56
→ yupog2003: 嗯嗯，確實是要用大的當root，小的attach上去，感謝 01/23 17:57
→ yupog2003: 模擬網頁上面有給我們兩個union by rank的選項： 01/23 17:58
→ yupog2003: 1.Rank = # of nodes, 2.Rank = estimated height 01/23 17:59
→ yupog2003: 看來的確如A大所說，兩者皆可 01/23 17:59
→ Transfat: 這樣,用union-by-rank我把號碼比較大的當Root值比較大 01/23 20:09
→ Transfat: 最後Find-Set()兩個我都回傳x16 01/23 20:09
→ yupog2003: Find-Set應該有沒有用union-by-rank和path-compression 01/23 20:12
→ yupog2003: 結果都會一樣？只是速度上的差異而已，確認一下觀念 01/23 20:13
→ AkariAkaza: 我是覺得除了5、6、7、8其他都有可能 01/23 20:19
推 Transfat: 結果不會一樣吧? 不同Union方法最後Find-set可能就會不 01/23 20:20
→ Transfat: 一樣 01/23 20:20
→ yupog2003: 嗯嗯對，有沒有用union-by-rank的Find-Set應該不一樣 01/23 20:21
→ yupog2003: path-compression應該沒差？ 01/23 20:21
推 Transfat: path-compression應該是沒差 01/23 20:23
→ yupog2003: 嗯嗯好的，感謝你們 01/23 20:26