[理工] 105 台大 電機丙 資演

作者: jerry900287 (滷蛋)   2017-12-14 11:14:36
如圖 https://i.imgur.com/TNyu9XJ.png
想請問一下各位大大的想法
因為我查了兩份別人寫的解答
有人寫 True
有人寫 False 因為( O(1) )
我覺得是 False
但不是 O(1) 因為他問的是點到點之間的Path不是Edge
然後做法是 DFS 去尋找
又它是 adjacency matrix
所以是 O ( V^2 )
不知道我的想法對不對?
感謝!!
作者: sarsman (DeNT15T♠)   2017-12-15 14:50:00
台大電機丙的資結超愛出這種很微妙的題目qq
作者: nova06091   2017-12-15 15:56:00
電機丙不是考資結B嗎?
作者: yusheng88992 (搭小黃囉)   2017-12-16 14:01:00
我也覺得是false,用BFS或DFS以matrix下去找是否connected應該是O(V^2)

Links booklink

Contact Us: admin [ a t ] ucptt.com