106成大资结(7) （9）求详解 ccmvic PTT批踢踢实业坊

楼主: ccmvic (Vic) 2019-02-22 08:14:36

各位好
求这两题详解
https://i.imgur.com/q5i9QGL.jpg
https://i.imgur.com/ABfPaJL.jpg

作者: WachinMs (NK) 2019-02-22 08:45:00

7.用 dfs 找是否存在 back edge8. 先求 SCC 建构出component graph H ,对 H 做拓朴排序并验证他是否存在 linear chain

作者: oldelette (oldelette) 2019-02-22 08:56:00

可以请教一下为什么有拓扑就会等价有semi connected吗？

作者: eric131204 (暗女巫) 2019-02-22 08:59:00

因为只要两点有一点可以走到另一点就好，所以不用强连通，用SCC图作拓朴只要有一条路同方向连起来就可以保证所有在某个SCC的点可以走到另一个SCC的点。

作者: oldelette (oldelette) 2019-02-22 09:07:00

所以semi 定义是两点之间有单向path就算吗有估狗过但找不太到好像不是完全等于弱连通？

作者: eric131204 (暗女巫) 2019-02-22 09:12:00

弱连通不是在讲undirected吗？我不太确定

作者: oldelette (oldelette) 2019-02-22 09:20:00

Directed 才有分强弱吧因为有方向问题先谢谢e大！

作者: eric131204 (暗女巫) 2019-02-22 09:25:00

弱连通是把digraph视为undirected如果是连通就算吗

作者: oldelette (oldelette) 2019-02-22 09:41:00

应该是

作者: eric131204 (暗女巫) 2019-02-22 09:46:00

那就跟semi不一样吧，像rooted tree把edge画父到子的方向，那子点就互相走不到，但他也算弱连通吧？

作者: ekids1234 (∵:☆星痕╭☆) 2019-02-22 10:15:00

第7题要写 "不能" 对吧 ? 只在O(V)有点吃图要O(V+E)?

作者: CorkiN (柯基) 2019-02-22 10:18:00

那题题目意思是要你写一个算法决定图中是否有含cycle @@

作者: eric131204 (暗女巫) 2019-02-22 10:30:00

O(V)就可以了吧，只是找有没有cycle最多就检查V-1个edge，再超过就必有cycle了

作者: Rioronja (想show干话组) 2019-02-22 11:00:00

同意楼上虽然dfs是O(V+E) 但实际运作顶多O(V)

作者: rustw2010 (cherish) 2019-02-22 21:53:00

是要写algo版的吗

作者: nn410375yi (nnyi) 2019-02-23 12:10:00

先知第一题猛

作者: eric131204 (暗女巫) 2019-02-23 13:00:00

朝圣一下完全考一样

作者: alen0303 (艾伦零参智商负三) 2019-02-23 16:50:00

考题命中恭喜

作者: magic83v (R7) 2019-02-24 07:28:00

QQ不会写

继续阅读