大家好，想跟大家讨论一下最后一题，
题目大致是说undirected graph要求"strongly" connected components,
要求写出及分析算法。
我对于题目有些疑问，因为strongly connected应该是用来描述directed graph吧？
undirected graph就直接说(connected) components不是吗（还是有人看过这个说法？）
为此我查了书上的定义，
1.Discrete and Combinatorial Mathematics: An Applied Introduction, 5e by
Ralph P. Grimaldi
p.351, Definition 7.15
A directed graph G on V is called strongly connected ...
2.Fundamentals of Data Structures in C, 2e by Horowitz
p.270,
A directed graph G is said to be strongly connected iff for every
pair....
所以我认为题目的叙述是有瑕疵的，若是要求undirected graph的components，可用
DFS/BFS来解；
但若是求directed graph的strongly connected components，就比较困难，没看过
这个算法应该很难自己想出来，
Kosaraju's Algorithm
http://www.csie.ntnu.edu.tw/~u91029/Component.html#5
各位的看法如何呢？谢谢。
我写两个 一个direct graph找SCC 另外一个一题意等于undirect graph 上找component
作者:
sm02188612 (The Children 01)
2016-02-25 17:27:00直接写无向图CC = SCC了
作者:
odanaga (PixiyON)
2016-02-25 17:28:00我只写undirectedKosaraju我没搞懂过qq
我也只写无向 其实我觉得应该有人能写出大概神手总是有的
作者:
sm02188612 (The Children 01)
2016-02-25 17:30:00有向图的情况, 用dfs找finish time,再把图上边都转向,从finish time最晚的从新跑一次dfs某本algo名校秘笈上写的那套,不晓得有无记错
欸欸想起来了 的确有这东西当下完全忘记 看来不是神手也能写 只是我太废QQ
作者:
odanaga (PixiyON)
2016-02-25 17:35:00重点就那个转向 要写完整不知道要想多久
作者:
sm02188612 (The Children 01)
2016-02-25 17:37:00记得是用adjacency matrix,把矩阵取转置应该可吧
作者:
odanaga (PixiyON)
2016-02-25 17:39:00应该可写undirected就没啥困难
作者: jackfantasy (jackfantasy) 2016-02-25 17:45:00
原来是考无向 我看成有向然后写SCC的algo了!!!如果是无向 那G转不转G'根本没差因为矩阵是对称的
作者:
odanaga (PixiyON)
2016-02-25 17:49:00我忘记scc是啥了所以XD
作者:
kev72806 (Taipei 101)
2016-02-25 18:09:00我做的题目跟书上写都是 direct scc .. 当下也傻眼
作者:
leo258x (TastyFeeder)
2016-02-25 18:10:00我写undirected 所以等价CC话说考成大好像很多人 还好我同学已经上榜 不抢名额0.0
作者:
odanaga (PixiyON)
2016-02-25 18:16:00推文大概有一半正取 目测
作者:
leo258x (TastyFeeder)
2016-02-25 18:17:00感觉只剩我要考了
作者:
odanaga (PixiyON)
2016-02-25 18:34:00假如手写改的松 应该就靠选择决胜负吧交大快出来了 大家集气！交大出来啦 甲组爽辣!!!!!
作者:
leo258x (TastyFeeder)
2016-02-25 18:42:00甲组备2 乙组正取
作者:
odanaga (PixiyON)
2016-02-25 18:43:00结果大家都不考成大了(?)
作者:
leo258x (TastyFeeder)
2016-02-25 18:51:00我会去 有个同学目前只有中央 会去陪考
作者:
sm02188612 (The Children 01)
2016-02-25 19:04:003x满稳的吧
作者:
odanaga (PixiyON)
2016-02-25 19:10:00没关系 有台大我读台大 集气 QQ
作者:
odanaga (PixiyON)
2016-02-25 19:13:00对阿也是有人台大正取其他miss 不怕 集气 !
作者:
odanaga (PixiyON)
2016-02-25 19:19:00集气!
作者:
leo258x (TastyFeeder)
2016-02-25 19:39:00g 大会备上拉 而且你台大也会
作者:
yaxauw (yaxauw)
2016-02-25 20:15:00g大我甲组也备3x诶 但现在在考虑去多工 有正取
作者: jackfantasy (jackfantasy) 2016-02-25 21:47:00
g大加油 在这版解那么多题帮那么多人了 会有好报的!
作者:
dslin (Magic)
2016-02-25 21:48:00g大OK的~好心有好报~!
作者:
odanaga (PixiyON)
2016-02-25 21:50:00好心有好报
作者:
irenelove (irenelove)
2016-02-26 03:32:00帮g大集气！