作者mqazz1 (无法显示)
站内Prob_Solve
标题[问题] Kosaraju求SCC
时间Tue Aug 30 19:07:22 2011
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