推 s06i06: If那行沒講怎麼找的 如果linear search 是O(|V|^2) 12/31 14:50
推 TWkobe: If 那段應該寫成迴圈一個一個比對最簡易 12/31 15:04
→ TampaBayRays: 所以我要假設G是一個adjancency matrix 12/31 15:06
→ TampaBayRays: V€adj.[B]就去測那個欄位是不是1就好 12/31 15:06
→ TampaBayRays: 不過他的input只有A B 12/31 15:06
→ TampaBayRays: 不是應該要有個G嗎？ 12/31 15:06
→ TampaBayRays: 不管是用什麼來存那個圖？ 12/31 15:06
推 s06i06: 我覺得可以用hash? A相鄰點的丟進hash table,再檢測B相鄰 12/31 15:07
→ s06i06: 的點有沒有在table裡,有個話count++ 12/31 15:07
→ TampaBayRays: 我原本也想用迴圈，不過他的input沒有讓我傳矩陣， 12/31 15:07
→ TampaBayRays: 寫起來毛毛的XD 12/31 15:07
→ s06i06: 這樣O(|V|) 12/31 15:08
→ s06i06: 用adjMatrix是O(|V|^2)題目要求要最佳化運算量 12/31 15:11
推 TWkobe: 也可以用bfs喔 12/31 15:11
推 TWkobe: 用bfs code超簡單 12/31 15:14
→ TWkobe: 只要將a,b兩個node各別作一次的enqueue adj vertex 12/31 15:15
→ TWkobe: 然後dequeue兩個queue來比對 12/31 15:16
→ TampaBayRays: 用bfs的前提是不是要把相鄰node由小到大enqueue? 12/31 15:17
推 TWkobe: 謝謝樓上補充 忘了假設這前題 12/31 15:20
→ TWkobe: 反正他題目要儘量優化 這樣假設應該ok 12/31 15:21
→ TampaBayRays: 那我直接假設用adjacency matrix存 12/31 15:26
→ TampaBayRays: 然後跑for i = 1 to |v| 12/31 15:26
→ TampaBayRays: If G(i,a)=1 and G(i,b)=1 then count++ 12/31 15:26
→ TampaBayRays: 這樣好像更快？就O(v) 12/31 15:26
推 TWkobe: 可是你a,b兩個graph這樣只有scan一點吧 12/31 15:29
→ TampaBayRays: 什麼意思？ 12/31 15:37
→ TampaBayRays: A B不是在同一張圖上嗎？ 12/31 15:38
推 TWkobe: 我的意思是你用舉陣是二維 你給了i只有一維阿 12/31 15:44
推 TWkobe: 噢我誤會了 應該可以 12/31 15:46
→ TampaBayRays: 好喔 12/31 16:00
→ TampaBayRays: 不過這樣寫出來沒幾句話就15分XD 12/31 16:00
推 TMDTMD2487: 用matrix跟你一樣 或是用adj list 但是點由大到小存在 01/01 17:43
→ TMDTMD2487: 裡面應該也可以八 應該八@@ 01/01 17:43
推 moneylon: 有大大能分享 用bfs的寫法嗎 小弟太菜了 01/02 10:48
→ TampaBayRays: 大概是這樣？ 01/02 16:31