作者TampaBayRays (光芒今年拿冠軍)
看板Grad-ProbAsk
標題[理工] 105 成大 程式設計
時間Sun Dec 31 13:56:15 2017
https://i.imgur.com/5vO858Y.jpg
https://i.imgur.com/FHjB1fG.jpg
請問這一題我這樣寫可以嗎？
有什麼bug嗎？
感謝～
-----
Sent from JPTT on my iPhone
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 49.218.96.254
※ 文章網址: https://webptt.com/m.aspx?n=bbs/Grad-ProbAsk/M.1514699780.A.241.html
1F：推 s06i06: If那行沒講怎麼找的 如果linear search 是O(|V|^2) 12/31 14:50
2F：推 TWkobe: If 那段應該寫成迴圈一個一個比對最簡易 12/31 15:04
3F：→ TampaBayRays: 所以我要假設G是一個adjancency matrix 12/31 15:06
4F：→ TampaBayRays: V€adj.[B]就去測那個欄位是不是1就好 12/31 15:06
5F：→ TampaBayRays: 不過他的input只有A B 12/31 15:06
6F：→ TampaBayRays: 不是應該要有個G嗎？ 12/31 15:06
7F：→ TampaBayRays: 不管是用什麼來存那個圖？ 12/31 15:06
8F：推 s06i06: 我覺得可以用hash? A相鄰點的丟進hash table,再檢測B相鄰 12/31 15:07
9F：→ s06i06: 的點有沒有在table裡,有個話count++ 12/31 15:07
10F：→ TampaBayRays: 我原本也想用迴圈，不過他的input沒有讓我傳矩陣， 12/31 15:07
11F：→ TampaBayRays: 寫起來毛毛的XD 12/31 15:07
12F：→ s06i06: 這樣O(|V|) 12/31 15:08
13F：→ s06i06: 用adjMatrix是O(|V|^2)題目要求要最佳化運算量 12/31 15:11
14F：推 TWkobe: 也可以用bfs喔 12/31 15:11
15F：推 TWkobe: 用bfs code超簡單 12/31 15:14
16F：→ TWkobe: 只要將a,b兩個node各別作一次的enqueue adj vertex 12/31 15:15
17F：→ TWkobe: 然後dequeue兩個queue來比對 12/31 15:16
18F：→ TampaBayRays: 用bfs的前提是不是要把相鄰node由小到大enqueue? 12/31 15:17
19F：推 TWkobe: 謝謝樓上補充 忘了假設這前題 12/31 15:20
20F：→ TWkobe: 反正他題目要儘量優化 這樣假設應該ok 12/31 15:21
21F：→ TampaBayRays: 那我直接假設用adjacency matrix存 12/31 15:26
22F：→ TampaBayRays: 然後跑for i = 1 to |v| 12/31 15:26
23F：→ TampaBayRays: If G(i,a)=1 and G(i,b)=1 then count++ 12/31 15:26
24F：→ TampaBayRays: 這樣好像更快？就O(v) 12/31 15:26
25F：推 TWkobe: 可是你a,b兩個graph這樣只有scan一點吧 12/31 15:29
26F：→ TampaBayRays: 什麼意思？ 12/31 15:37
27F：→ TampaBayRays: A B不是在同一張圖上嗎？ 12/31 15:38
28F：推 TWkobe: 我的意思是你用舉陣是二維 你給了i只有一維阿 12/31 15:44
29F：推 TWkobe: 噢我誤會了 應該可以 12/31 15:46
30F：→ TampaBayRays: 好喔 12/31 16:00
31F：→ TampaBayRays: 不過這樣寫出來沒幾句話就15分XD 12/31 16:00
32F：推 TMDTMD2487: 用matrix跟你一樣 或是用adj list 但是點由大到小存在 01/01 17:43
33F：→ TMDTMD2487: 裡面應該也可以八 應該八@@ 01/01 17:43
34F：推 moneylon: 有大大能分享 用bfs的寫法嗎 小弟太菜了 01/02 10:48
36F：→ TampaBayRays: 大概是這樣？ 01/02 16:31