0001 template <typename Tv, typename Te> void Graph<Tv, Te>::bcc ( int s ) { //基于DFS的BCC分解算法 0002 reset(); int clock = 0; int v = s; Stack<int> S; //栈S用以记录已访问的顶点 0003 do 0004 if ( UNDISCOVERED == status ( v ) ) { //一旦发现未发现的顶点(新连通分量) 0005 BCC ( v, clock, S ); //即从该顶点出发启动一次BCC 0006 S.pop(); //遍历返回后,弹出栈中最后一个顶点——当前连通域的起点 0007 } 0008 while ( s != ( v = ( ++v % n ) ) ); 0009 } 0010 #define hca(x) (fTime(x)) //利用此处闲置的fTime[]充当hca[] 0011 template <typename Tv, typename Te> //顶点类型、边类型 0012 void Graph<Tv, Te>::BCC ( int v, int& clock, Stack<int>& S ) { //assert: 0 <= v < n 0013 hca ( v ) = dTime ( v ) = ++clock; status ( v ) = DISCOVERED; S.push ( v ); //v被发现并入栈 0014 for ( int u = firstNbr ( v ); -1 < u; u = nextNbr ( v, u ) ) //枚举v的所有邻居u 0015 switch ( status ( u ) ) { //并视u的状态分别处理 0016 case UNDISCOVERED: 0017 parent ( u ) = v; type ( v, u ) = TREE; BCC ( u, clock, S ); //从顶点u处深入 0018 if ( hca ( u ) < dTime ( v ) ) //遍历返回后,若发现u(通过后向边)可指向v的真祖先 0019 hca ( v ) = min ( hca ( v ), hca ( u ) ); //则v亦必如此 0020 else //否则,以v为关节点(u以下即是一个BCC,且其中顶点此时正集中于栈S的顶部) 0021 while ( u != S.pop() ); //弹出当前BCC中(除v外)的所有节点,可视需要做进一步处理 0022 break; 0023 case DISCOVERED: 0024 type ( v, u ) = BACKWARD; //标记(v, u),并按照“越小越高”的准则 0025 if ( u != parent ( v ) ) hca ( v ) = min ( hca ( v ), dTime ( u ) ); //更新hca[v] 0026 break; 0027 default: //VISITED (digraphs only) 0028 type ( v, u ) = ( dTime ( v ) < dTime ( u ) ) ? FORWARD : CROSS; 0029 break; 0030 } 0031 status ( v ) = VISITED; //对v的访问结束 0032 } 0033 #undef hca