[codebook] SCC - Tarjan

程式碼, codebook
12345678910111213/*Strong Connected ComponentTarjan's algorithm算法描述：使用 dfn 紀錄 DFS 順序stack 紀錄點如果能夠走回較小的 dfn代表存在強連通分量於是退棧將強連通點都取出反覆操作便可求得所有強連通分量用相鄰矩陣複雜度為 O(V^2)，若是相鄰列表則為 O(V+E)*/ Pseudo Code: 123456789101112131415161718192021222324252627282930313233graph G = ( V, E )create S as stackProcedure DFS( integer u ) Index = Index + 1 dfn [ u ] = low [ u ] = Index push u into S for each ( u, v ) in E if v is not visited then tarjan( v ) if u is in S then low [ u ] = min ( low [ u ], low [ v ] ) end for if dfn [ u ] is equal to low [ u ] then do tmp = top element in S pop element in S while tmp is not uEnd ProcedureProcedure tarjan() for u = 1 to n if u is not visited then DFS( i ) end forEnd Procedure

閱讀全文