作者ccmvic (Vic)
看板Grad-ProbAsk
标题106成大资结(7) （9）求详解
时间Fri Feb 22 08:14:36 2019
各位好
求这两题详解
https://i.imgur.com/q5i9QGL.jpg
https://i.imgur.com/ABfPaJL.jpg
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 39.12.162.145
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Grad-ProbAsk/M.1550794479.A.2EB.html
※ 编辑: ccmvic (39.12.162.145), 02/22/2019 08:17:30
1F：推 WachinMs: 7.用 dfs 找是否存在 back edge 02/22 08:45
2F：→ WachinMs: 8. 先求 SCC 建构出component graph H ,对 H 做拓朴排 02/22 08:45
3F：→ WachinMs: 序并验证他是否存在 linear chain 02/22 08:45
4F：推 oldelette: 可以请教一下 为什麽有拓扑 就会等价有semi connected 02/22 08:56
5F：→ oldelette: 吗？ 02/22 08:56
6F：推 eric131204: 因为只要两点有一点可以走到另一点就好，所以不用强连 02/22 08:59
7F：→ eric131204: 通，用SCC图作拓朴只要有一条路同方向连起来就可以保 02/22 08:59
8F：→ eric131204: 证所有在某个SCC的点可以走到另一个SCC的点。 02/22 08:59
9F：→ oldelette: 所以semi 定义是两点之间有单向path就算吗 有估狗过但 02/22 09:07
10F：→ oldelette: 找不太到 好像不是完全等於弱连通？ 02/22 09:07
11F：推 eric131204: 弱连通不是在讲undirected吗？我不太确定 02/22 09:12
12F：→ oldelette: Directed 才有分强弱吧 因为有方向问题 先谢谢e大！ 02/22 09:20
13F：推 eric131204: 弱连通是把digraph视为undirected如果是连通就算吗 02/22 09:25
14F：推 oldelette: 应该是 02/22 09:41
15F：推 eric131204: 那就跟semi不一样吧，像rooted tree把edge画父到子的 02/22 09:46
16F：→ eric131204: 方向，那子点就互相走不到，但他也算弱连通吧？ 02/22 09:46
17F：→ ekids1234: 第7题要写 "不能" 对吧 ? 只在O(V)有点吃图 要O(V+E)? 02/22 10:15
18F：→ CorkiN: 那题题目意思是要你写一个演算法决定图中是否有含cycle @@ 02/22 10:18
19F：推 eric131204: O(V)就可以了吧，只是找有没有cycle最多就检查V-1个ed 02/22 10:30
20F：→ eric131204: ge，再超过就必有cycle了 02/22 10:30
21F：推 Rioronja: 同意楼上 虽然dfs是O(V+E) 但实际运作顶多O(V) 02/22 11:00
22F：推 rustw2010: 是要写algo版的吗 02/22 21:53
23F：推 nn410375yi: 先知 第一题猛 02/23 12:10
24F：推 eric131204: 朝圣一下 完全考一样 02/23 13:00
25F：推 alen0303: 考题命中 恭喜 02/23 16:50
26F：嘘 magic83v: QQ不会写 02/24 07:28