[理工] 105 成大程式設計 TampaBayRays PTT批踢踢實業坊

作者: TampaBayRays (光芒今年拿冠軍) 2017-12-31 13:56:15

https://i.imgur.com/5vO858Y.jpg
https://i.imgur.com/FHjB1fG.jpg
請問這一題我這樣寫可以嗎？
有什麼bug嗎？
感謝～

作者: s06i06 (三條魚) 2017-12-31 14:50:00

If那行沒講怎麼找的如果linear search 是O(|V|^2)

作者: TWkobe (中華柯比) 2017-12-31 15:04:00

If 那段應該寫成迴圈一個一個比對最簡易

作者: TampaBayRays (光芒今年拿冠軍) 2017-12-31 15:06:00

所以我要假設G是一個adjancency matrixV€adj.[B]就去測那個欄位是不是1就好不過他的input只有A B不是應該要有個G嗎？不管是用什麼來存那個圖？

作者: s06i06 (三條魚) 2017-12-31 15:07:00

我覺得可以用hash? A相鄰點的丟進hash table,再檢測B相鄰的點有沒有在table裡,有個話count++

作者: TampaBayRays (光芒今年拿冠軍) 2017-12-31 15:07:00

我原本也想用迴圈，不過他的input沒有讓我傳矩陣，寫起來毛毛的XD

作者: s06i06 (三條魚) 2017-12-31 15:08:00

這樣O(|V|)用adjMatrix是O(|V|^2)題目要求要最佳化運算量

作者: TWkobe (中華柯比) 2017-12-31 15:11:00

也可以用bfs喔用bfs code超簡單只要將a,b兩個node各別作一次的enqueue adj vertex然後dequeue兩個queue來比對

作者: TampaBayRays (光芒今年拿冠軍) 2017-12-31 15:17:00

用bfs的前提是不是要把相鄰node由小到大enqueue?

作者: TWkobe (中華柯比) 2017-12-31 15:20:00

謝謝樓上補充忘了假設這前題反正他題目要儘量優化這樣假設應該ok

作者: TampaBayRays (光芒今年拿冠軍) 2017-12-31 15:26:00

那我直接假設用adjacency matrix存然後跑for i = 1 to |v|If G(i,a)=1 and G(i,b)=1 then count++這樣好像更快？就O(v)

作者: TWkobe (中華柯比) 2017-12-31 15:29:00

可是你a,b兩個graph這樣只有scan一點吧

作者: TampaBayRays (光芒今年拿冠軍) 2017-12-31 15:37:00

什麼意思？A B不是在同一張圖上嗎？

作者: TWkobe (中華柯比) 2017-12-31 15:44:00

我的意思是你用舉陣是二維你給了i只有一維阿噢我誤會了應該可以

作者: TampaBayRays (光芒今年拿冠軍) 2017-12-31 16:00:00

好喔不過這樣寫出來沒幾句話就15分XD

作者: TMDTMD2487 (ㄚ冰) 2016-01-01 17:43:00

用matrix跟你一樣或是用adj list 但是點由大到小存在裡面應該也可以八應該八@@

作者: moneylon (bencool) 2016-01-02 10:48:00

有大大能分享用bfs的寫法嗎小弟太菜了

作者: TampaBayRays (光芒今年拿冠軍) 2016-01-02 16:31:00

繼續閱讀