作者b76516 (阿聰)
看板Grad-ProbAsk
標題[理工] [資結]-交大96-資訊
時間Tue Jan 5 21:17:46 2010
請問一下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
1F：推 cansister:應該是parent[x]＝Mystery(parent[x])的回傳值 01/05 21:37
2F：→ b76516:怪了 如果是這樣的話 所有的點都指向root了 01/05 21:48
3F：推 uminchu185:記得這題好像是find()的path compression. 01/05 22:19
4F：推 cansister:對阿指向root沒錯阿 就是要找他的root阿 01/05 22:26
5F：推 cansister:所以圖形會變成，Y到root路徑上的node最後都改指向root 01/05 22:37
6F：→ b76516:喔 我的意思是 全部的點都指向整棵樹的ROOT了 01/05 22:39