0001 template <typename Tv, typename Te> void Graph<Tv, Te>::bcc( Rank s ) { //基于DFS的BCC分解算法
0002    reset(); Rank clock = 0; Rank v = s; Stack<Rank> 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( Rank v, Rank& clock, Stack<Rank>& 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