[理工] 演算法 DFS找strong connected component

[mogahuang (mogahuang)]

各位大大安安

請問利用兩次DFS 找 scc 在第二步是用第一次v.f的大小選點，但要如何選才能切割出scc?

http://i.imgur.com/2nwLtDN.jpg

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 122.116.83.181
※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1479033283.A.09C.html
→ gigayaya: 在srep.2走出一個cycle就是一個scc
→ ken52011219: 以G^T為例，G的u.f最大者為b(16)以它作為起點
→ ken52011219: DFS可選擇做a(14) or f(4)因 由大到小所以G^T選擇a
→ ken52011219: 我搞混了 只剩a可以做所以選擇a
→ ken52011219: 應該看c 因c可選擇d(9) g(7)所以G^T DFS(c)選擇d
→ ken52011219: 做完一個CYCLE為一個強連通
推 kyuudonut: 一直覺得這個解法超妙的 值得推一下XD
→ mogahuang: Gigi大 可是在原本的圖他不是也可以走一個cycle嗎？？
→ mogahuang: 我懂了，是用第一次的結束時間在第二次的圖上跑，因為
→ mogahuang: 單向會造成不連通，所以在做DFS時如果是scc的話會回到
→ mogahuang: 起點這樣嗎？？
→ ken52011219: 可以看成類似第一個DFS是找出單方向為connect的點
→ ken52011219: 第二次DFS找出 另外一個方向的connect
→ ken52011219: 且為第一個DFS找出的connect的基礎上
→ gigayaya: Step2的圖是原本圖的反向 挑的順序是圖1DFS結束時間從
→ gigayaya: 最大的開始挑
推 aa06697: 在原圖走不出相反圖的cycle
推 windwaker112: https://i.imgur.com/onY7L36.jpg