作者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/cn.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