[問題] Kosaraju求SCC
看板Prob_Solve (計算數學 Problem Solving)作者mqazz1 (無法顯示)時間13年前 (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
推
08/30 19:47, , 1F
08/30 19:47, 1F
Prob_Solve 近期熱門文章
PTT數位生活區 即時熱門文章
