[理工] 105 交大资演 Union
楼主: Gabino (YenC) 2016-12-26 14:33:00
想请问大家第9大题的第(26)题
(a)选项
翻了圣经本是提到min{m,n-1}次Union
细看之后感觉和"at most m Unions"好像又没有冲突
(b)选项
照上一题来看
最多应该是2m次或是2(n-1)次
不知道这两个选项大家都怎思考的?
楼主: Gabino (YenC) 2016-12-27 17:49:00
了解 我的战友也跟你表示一样的意思 只不过题库班老师表示2m次 QQ 交大题目每次都得猜他在问啥..
作者: aa06697 (todo se andarà) 2016-12-27 10:29:00
喔喔～ 昨天看太快我以为最后一句的find意思是指find function会往上找几个点XD 如果是指最多m个function 那我也不知道这句话的意思了看有没有其他人知道qqunion会先find两次没错今天上到题库班 老师b的讲法跟我讲法一样唷 就是那个m finds想表达的意思是find要花 O(m)
作者: aa06697 (todo se andarà) 2016-12-26 15:39:00
a意思是要把forest union成一个tree? 是的话 n个点都是独立tree 0个边 要union n-1次 b的话最惨就是n个点是一个直线的tree 有m个边 从最底部到root path = m补充一下是最多union n-1次@@
楼主: Gabino (YenC) 2016-12-26 17:39:00
aa大说的路径最长为m我大概了解了 但不太懂这和(b)的最后一句话有什么关联，我以为一次Union之前要做两次find 不知道这样想是不是错的