大家好，想跟大家討論一下最後一題，
題目大致是說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大集氣！