Re: [理工] 102 台大電機丙 資結 對答案

[PTT007 (鍵盤007)]

請問第3題要怎麼算？

還有第2題和第23題正確的複雜度應該是多少？

謝謝~

※ 引述《olderbrother (大蜘蛛)》之銘言：
: 題目
: http://exam.lib.ntu.edu.tw/sites/default/files/exam/graduate/102/102409.pdf
: 我寫的答案
: (A:True, B:False, 考卷上是這樣標的...)
:  1. B
:  2. B
:  3. A
:  4. B
:  5. A
:  6. B  (感謝 A4P8T6X9 大大)
:  7. B
:  8. B
:  9. B
: 10. A
: 11. A
: 12. A
: 13. B
: 14. A
: 15. B
: 16. A
: 17. B
: 18. B  (感謝 a5120265 大大)
: 19. A  (感謝 A4T8T6X9 大大)
: 20. B  (感謝 A4T8T6X9 大大)
: 21. B
: 22. A
: 23. B
: 24. A
: 25. B
: 6 19 20 要麻煩大家幫忙湊答案了...

--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 220.136.107.253
→ A4P8T6X9:2.O(n) 23.對兩個點各做一次DFS即可吧。
→ A4P8T6X9:3.排列有n!種，每種要印出來需要n。
→ PTT007:感謝~~!!
→ johnny87901:不是做DFS巴 是做short path of two vertexs 是O(n^3)
推 a5120265:做兩次DFS會快一點吧O(n^2)，當然用Floyid解就是O(n^3)
推 a5120265:用DFS做也可以避免graph without weight的狀況
→ a5120265:畢竟只是要判斷有沒有相連而已題目應該不要求short path
→ a5120265:一點想法　參考參考