[問題] Kosaraju求SCC

看板Prob_Solve作者mqazz1 (無法顯示)時間14年前 (2011/08/30 19:07)推噓1(1推 0噓 0→)

留言1則, 1人參與討論串1/1

Kosaraju求SCC 1. DFS(G), 求每node的finish time 2. DFS(G^T), 依finish time的遞減順序執行已知 C 和 C' 為相異的SCC, u為C中一頂點, v為C'中一頂點, (u,v)屬於E f(C) > f(C') //finish time 請問要怎麼用這些條件證明Kosaraju是正確的? 謝謝 -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 61.228.26.116

推

suhorng

08/30 19:47, , 1^F

08/30 19:47, 1^F

‣ 返回看板[ Prob_Solve ] 研討

‣ 更多 mqazz1 的文章

文章代碼(AID): #1ENCHiDd (Prob_Solve)