[理工] 105 交大資演 Union

看板Grad-ProbAsk作者 (YenC)時間7年前 (2016/12/26 14:33), 編輯推噓1(1推 0噓 14→)
留言15則, 2人參與, 最新討論串1/1
http://i.imgur.com/QQNt6aq.jpg
想請問大家第9大題的第(26)題 (a)選項 翻了聖經本是提到min{m,n-1}次Union 細看之後感覺和"at most m Unions"好像又沒有衝突 (b)選項 照上一題來看 最多應該是2m次或是2(n-1)次 不知道這兩個選項大家都怎思考的? -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 60.251.229.159 ※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1482733983.A.A40.html
推
12/26 15:39, , 1F
a意思是要把forest union成一個tree? 是的話 n個點都是獨
12/26 15:39, 1F
→
12/26 15:39, , 2F
立tree 0個邊 要union n-1次 b的話最慘就是n個點是一個直
12/26 15:39, 2F
→
12/26 15:39, , 3F
線的tree 有m個邊 從最底部到root path = m
12/26 15:39, 3F
→
12/26 15:43, , 4F
補充一下是最多union n-1次@@
12/26 15:43, 4F
→
12/26 17:39, , 5F
aa大說的路徑最長為m我大概瞭解了 但不太懂這和(b)的最後
12/26 17:39, 5F
→
12/26 17:39, , 6F
一句話有什麼關聯，我以為一次Union之前要做兩次find 不
12/26 17:39, 6F
→
12/26 17:39, , 7F
知道這樣想是不是錯的
12/26 17:39, 7F
→
12/27 10:29, , 8F
喔喔～ 昨天看太快我以為最後一句的find意思是指find fun
12/27 10:29, 8F
→
12/27 10:29, , 9F
ction會往上找幾個點XD 如果是指最多m個function 那我也
12/27 10:29, 9F
→
12/27 10:29, , 10F
不知道這句話的意思了看有沒有其他人知道qq
12/27 10:29, 10F
→
12/27 10:29, , 11F
union會先find兩次沒錯
12/27 10:29, 11F
→
12/27 15:53, , 12F
今天上到題庫班 老師b的講法跟我講法一樣唷 就是那個m fi
12/27 15:53, 12F
→
12/27 15:53, , 13F
nds想表達的意思是find要花 O(m)
12/27 15:53, 13F
→
12/27 17:49, , 14F
瞭解 我的戰友也跟你表示一樣的意思 只不過題庫班老師表
12/27 17:49, 14F
→
12/27 17:49, , 15F
示2m次 QQ 交大題目每次都得猜他在問啥..
12/27 17:49, 15F
‣ 更多 Gabino 的文章
文章代碼(AID): #1OOBcVf0 (Grad-ProbAsk)