[理工] 算法 DFS找strong connected component mogahuang PTT批踢踢实业坊

楼主: mogahuang (mogahuang) 2016-11-13 18:34:41

各位大大安安
请问利用两次DFS 找 scc 在第二步是用第一次v.f的大小选点，但要如何选才能切割出scc?
http://i.imgur.com/2nwLtDN.jpg

作者: windwaker112 (阿茄) 2016-11-14 16:14:00

作者: gigayaya (gigayaya) 2016-11-13 18:58:00

在srep.2走出一个cycle就是一个scc

作者: ken52011219 (呱) 2016-11-13 19:01:00

以G^T为例，G的u.f最大者为b(16)以它作为起点DFS可选择做a(14) or f(4)因由大到小所以G^T选择a我搞混了只剩a可以做所以选择a应该看c 因c可选择d(9) g(7)所以G^T DFS(c)选择d做完一个CYCLE为一个强连通

作者: kyuudonut (å–„è‰¯è€ç™¾å§“) 2016-11-13 19:14:00

一直觉得这个解法超妙的值得推一下XD

楼主: mogahuang (mogahuang) 2016-11-13 19:27:00

Gigi大可是在原本的图他不是也可以走一个cycle吗？？我懂了，是用第一次的结束时间在第二次的图上跑，因为单向会造成不连通，所以在做DFS时如果是scc的话会回到起点这样吗？？

作者: ken52011219 (呱) 2016-11-13 19:47:00

可以看成类似第一个DFS是找出单方向为connect的点第二次DFS找出另外一个方向的connect且为第一个DFS找出的connect的基础上

作者: gigayaya (gigayaya) 2016-11-13 19:48:00

Step2的图是原本图的反向挑的顺序是图1DFS结束时间从最大的开始挑

作者: aa06697 (todo se andarà) 2016-11-13 20:35:00

在原图走不出相反图的cycle

继续阅读