[問題] Kosaraju求SCC

[mqazz1 (無法顯示)]

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:http://lcm.csa.iisc.ernet.in/dsa/node171.html