[理工] [資結]-98成大

[polomoss (小澤)]

http://ppt.cc/I2QT



問一下第一題跟第二題的答案是什麼??



兩題選擇題

--
     ◤    ◥  答      ◤    ◥  拉      ◤    ◥  米      ◤    ◥  哆
   Σ ◆  ◆   蚊    Σ ◆  ◆   肥    Σ ◆  ◆   開    Σ ◆  ◆   啦
        ︵     吸         ︵     兒         ︵     喇         ︵     太
    ◣++++++◢        ◣++++++◢        ◣++++++◢ 雞     ◣++++++◢ 裸
◥▇▆@ ≡ @▆▇◤     Ψ ≡ Ψ          ▄ ≡ ▄  囉  ▄▄▄ ≡ ▄▄▄
        ▅                ▅          ▄/   ▅   \▄          ▅  ＡΓＶＩＳＳ

--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 122.116.14.2
推 FRAXIS:第二題應該是c
→ polomoss:只有C而已喔~?
→ yesa315:B錯 A若單點有LOOP C錯
→ yesa315:        打錯 C對 D錯
推 Lautreamont:請教一下  B錯在哪裡?
推 assassin88:也想問B錯在哪?
→ assassin88:還有D..XD
推 Lautreamont:D 會不會是因為path是在G 而不是在DFS tree?
→ Lautreamont:sorry 我搞錯了 那沒差
→ polomoss:可以請問BD錯在哪嗎??
→ polomoss:還有第一題有人會嗎?? 15分耶
→ assassin88:成大三科難的就這一頁而已..Orz
推 willow02:D 有可能是cross edge?
推 sa074463:我也想問B錯在哪T^T
→ bearzoo:是不是nlogn阿??(不確定...)因為每次花logn...要做n次??
→ bearzoo:可是他好像也沒說要做n次....~"~(當我搞錯好了= =")
→ bearzoo:剛找到一篇文章http://0rz.tw/IDGxT 所以應該是dlogn??@@?
推 zkdzvy22:應該是d個兒子選最大的往上放  然後做logn層=>O(dlogn)
→ yesa315:樓上正解
→ jnjh9901:D對吧!  這是無向圖 有邊 用DFS x不是y的descendant 那
→ jnjh9901:y就是x的descendant   有錯請指正