Re: [理工] [資結]-交大96-資訊

[b76516 (阿聰)]

※ 引述《cansister (cansister)》之銘言：
※ 引述《b76516 (阿聰)》之銘言：
: 請問一下96年交大資訊資結第5題
: http://www2.lib.nctu.edu.tw/n_exam/exam96/cslz/cslz1001.pdf
: 請問他給的程式碼
: Procedure Mystery(x)
: {
:  if(x is not equal to parent[x])
:   then parent[x] <- Mystery(parent[x]);
:  return parent[x];
: }
: parent[x] <- Mystery(parent[x])
: 請問這行程式碼的意思是
: Mystery(parent[x])的回傳值 指向 parent[x]
: 還是 parent[x]＝Mystery(parent[x])的回傳值
: 謝謝

Consider the following input what will be the output and the rooted after
executing Mystery(Y).Draw the tree.

                           Root
                            ○

                      ↗ ↗ ↑ ↖ ↖
                    A○ ○F ○Y ○C ○B
                      ↖       ↗
                      D○    E○
                        ↖     ↖
                        G○    X○

如果Y為Mystery()的input時，最後結果圖形會變成上圖，
而Y→F→C→A→Root這條path上的node都會指向Root。

不知道你說的所有的點，是指整個圖形的點還是這條path上的點
所以我就畫圖這個圖來（有點醜XD）

================分隔線＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
先謝謝你阿
不過我的問題是 我畫出來 是圖形裡面所有的點都指向root了
例如以D為例
因為D不等於parent[D]＝A
所以parent[D]＝Mystery(parent[D])
也就是Mystery(A)
那Mystery(A)的回傳值就是ROOT
所以D的parent指向ROOT
請問我是哪裡有問題？
謝謝嚕





--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 220.134.129.184

--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 61.230.128.9
推 cansister:所以會變成A、D、B指向root，可是G還是指向D，C以下還是
→ cansister:指向A。
推 cansister:你上面敘述的都對，可是Root回傳給D不代表他會繼續傳給G
→ cansister:所以改變得只有call過Mystery()這function的點:D、A兩點
→ b76516:哎呀 我發現我題目看錯了 我以為全部的點都要call過 謝謝嚕
推 FRAXIS:其實這就類似Disjoint Set的Path Compression吧