0001 #define hca fTime //将闲置的fTime[]用作hca[]
0002 template <typename Tv, typename Te> //基于DFS，对当前连通分量做BCC分解
0003 void Graph<Tv, Te>::BCC(Rank v, Rank& clock, Stack<Rank>& S) { //0 <= v < n
0004    dTime(v) = ++clock;  status(v) = DISCOVERED;  S.push(v); //v被发现并入栈
0005    hca(v) = dTime(parent(v)); //以父亲的dTime为初始的hca；特别地，当v为起点时，就是自己的dTime
0006    for (Rank u = firstNbr(v); -1 != u; u = nextNbr(v, u)) //枚举v的所有邻居u
0007       switch (status(u)) { //并视u的状态分别处理（VISITED顶点在这里无需处理）
0008          case UNDISCOVERED: //发现TREE(v,u)
0009             parent(u) = v;  BCC(u, clock, S); //从顶点u处深入
0010             if (hca(u) < dTime(v)) //遍历返回后，若发现u（通过后向边）可指向v的真祖先
0011                hca(v) = min(hca(v), hca(u)); //则v亦必如此
0012             else //否则，以v为割点（u以下即是一个BCC，且其中顶点此时正集中于栈S的顶部）
0013                while (u != S.pop()); //弹出当前BCC中（除parent(u)外）的所有节点
0014             break;
0015          case DISCOVERED: hca(v) = min(hca(v), dTime(u));  break; //发现BACK(v,u)，更新hca[v]
0016       } //switch
0017    status(v) = VISITED; //对v的访问结束
0018 } //BCC: O(n+e)
0019 template <typename Tv, typename Te> void Graph<Tv, Te>::bcc(Rank s) { //对全图做BCC分解
0020    reset();  Stack<Rank> S; //栈S用以记录已访问的顶点
0021    for (Rank clock = 0, v = s; v < s+n; v++) //从s起顺次检视每个顶点
0022       if (UNDISCOVERED == status(v%n)) //一旦遇到尚未发现者
0023          { BCC(v%n, clock, S);  S.pop(); } //即对其所在的连通分量做BCC分解
0024 } //bcc