作者b76516 (阿聪)
看板Grad-ProbAsk
标题Re: [理工] [资结]-交大96-资讯
时间Wed Jan 6 00:21:30 2010
※ 引述《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
1F：推 cansister:所以会变成A、D、B指向root，可是G还是指向D，C以下还是 01/06 08:39
2F：→ cansister:指向A。 01/06 08:40
3F：推 cansister:你上面叙述的都对，可是Root回传给D不代表他会继续传给G 01/06 08:42
4F：→ cansister:所以改变得只有call过Mystery()这function的点:D、A两点 01/06 08:44
5F：→ b76516:哎呀 我发现我题目看错了 我以为全部的点都要call过 谢谢噜 01/06 09:04
6F：推 FRAXIS:其实这就类似Disjoint Set的Path Compression吧 01/06 09:19