[理工] 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

继续阅读