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

看板Grad-ProbAsk作者 (阿聰)時間16年前 (2010/01/05 21:17), 編輯推噓4(402)
留言6則, 3人參與, 最新討論串1/3 (看更多)
請問一下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])的回傳值 謝謝 -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 61.230.137.16

01/05 21:37, , 1F
應該是parent[x]=Mystery(parent[x])的回傳值
01/05 21:37, 1F

01/05 21:48, , 2F
怪了 如果是這樣的話 所有的點都指向root了
01/05 21:48, 2F

01/05 22:19, , 3F
記得這題好像是find()的path compression.
01/05 22:19, 3F

01/05 22:26, , 4F
對阿指向root沒錯阿 就是要找他的root阿
01/05 22:26, 4F

01/05 22:37, , 5F
所以圖形會變成,Y到root路徑上的node最後都改指向root
01/05 22:37, 5F

01/05 22:39, , 6F
喔 我的意思是 全部的點都指向整棵樹的ROOT了
01/05 22:39, 6F
文章代碼(AID): #1BGplzuR (Grad-ProbAsk)
文章代碼(AID): #1BGplzuR (Grad-ProbAsk)