作者ponwar87123 (干我屁事喔北七)
看板Grad-ProbAsk
标题[理工] 中央102资演 对答案及问问题
时间Tue Dec 17 16:13:14 2019
1.
(1)array不知道怎麽写进key跟string
(2)(3)(4)应该都挺简单的
(5)我是直接画树，但好像也要用array放？
2.也很简单
3.
(1)不可能 因为index14的parent为empty
(2)BDAFEGC
(3)ABDCEFG
(4)ABCDEFG
4.
(1)用BFS找出u到v的edge最大值，若新值比较小则把它替换掉，否则保留
(2)因为新加入edge必使MST行成cycle，再拿掉一边仍保持tree
(3)走path会是O(n)
5.
(1)也是用BFS，若找到某个点其附近的点都是黑色（无白色），表示其为leaf
(2)同2
(3)
这题不会
6.看不懂题目QQ
还请各位高手帮忙解题
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 101.12.102.127 (台湾)
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Grad-ProbAsk/M.1576570398.A.4B9.html
※ 编辑: ponwar87123 (101.12.102.127 台湾), 12/17/2019 16:14:33
1F：推 cry589036511: 第一题应该是指struct array 12/17 16:29
2F：→ cry589036511: 5-3用dfs 判断图上有无cycle 即可 12/17 16:59