[理工][軟體]99台大軟體設計
第5題
Give a pseudocode that determines whether or not an undirected graph
G=(V,E) contains a cycle. You need to show that your pseudocode runs
in O(V) time. You may assue that the adjacency-list representation
of G is given, and for each vertex u in V, Adj[u] consists of all the
vertices adjacent to u in G.
題目要求演算法需在O(V)內完成
想請問一下版上大大該怎麼做??
(是否可直接用DFS求解??其複雜度為Θ(V+E))
謝謝
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 59.126.0.166
推
12/12 02:14, , 1F
12/12 02:14, 1F
推
12/12 09:17, , 2F
12/12 09:17, 2F
→
12/12 15:58, , 3F
12/12 15:58, 3F
推
12/12 16:05, , 4F
12/12 16:05, 4F
→
12/12 16:05, , 5F
12/12 16:05, 5F
→
12/12 16:06, , 6F
12/12 16:06, 6F
→
12/12 16:07, , 7F
12/12 16:07, 7F
→
12/12 16:41, , 8F
12/12 16:41, 8F
→
12/12 16:41, , 9F
12/12 16:41, 9F
※ 編輯: peropero1 來自: 59.126.0.166 (12/12 16:42)
→
12/12 16:43, , 10F
12/12 16:43, 10F
推
12/13 18:25, , 11F
12/13 18:25, 11F
推
12/13 18:27, , 12F
12/13 18:27, 12F
→
12/13 18:52, , 13F
12/13 18:52, 13F
→
12/13 18:55, , 14F
12/13 18:55, 14F
→
08/09 10:59, , 15F
08/09 10:59, 15F
→
09/11 14:05, , 16F
09/11 14:05, 16F
→
12/15 00:28,
5年前
, 17F
12/15 00:28, 17F