strong-connected.png

很明显，Flood Fill并不能用来求强连通分量。但只使用BFS/DFS，我们可以给出一个求给定点所在强连通分量的方法：1) 从该点出发做一次BFS/DFS；2) 把所有边反向，再从这个点做一次BFS/DFS；3) 把两次搜索访问的顶点集合做一次交，就可以得到该点所在的极大强连通分量。如果用这种方法求所有强连通分量的话，需要对每个点做两次BFS/DFS，时间复杂度为O(n^2)。更好的方法是Kosaraju算法或Tarjan算法，这里只介绍Tarjan。

Tarjan算法中，图中每个节点维护两个属性：

1. dfu(i)：节点i在DFS中第dfu(i)个被访问到（时间戳）；
2. low(i)：DFS搜索树中，以节点i为根节点的子树中的节点集合记为T(i)。T(i)中的点在原图中所指向的点的集合记为S(i)。S(i)中最小的时间戳就是low(i)，low(i)可以用下面的递归式表示：
   low(i) = min(dfn(i), dfn(j), low(j)) (j为i的子节点)

Tarjan算法的描述如下：

1. 初始化一个空的栈和一个每访问一个节点加1的计时器
2. 对图做DFS，每次访问新的顶点时，设定dfn(i)为当前时间，把该节点压栈，接着求low(i)：对于还没被访问的后继节点j，递归访问j，low(i) = min(dfn(i), low(j))，对于已经访问过的后继节点k，low(i) = min(low(i), dfn(j))。如果最终得到的low(i) = dfn(i)，就把栈中当前节点以上的节点全部弹出，这些节点就是一个极大强连通分量

Tarjan算法只需要做一遍DFS，所以一定会终止，时间复杂度O(m+n)。

C++实现：

void tarjan(int u) {
    dfn[u] = low[u] = ++cnt;
    st[++top] = u;
    instack[u] = true;

    for(Edge *p = e[u]; p; p = p->next) {
        int v = p->dst;
        if(!dfn[v]) {
            tarjan(v);
            low[u] = std::min(low[u], low[v]);
        }
        else if(instack[v])
            low[u] = std::min(low[u], dfn[v]);
    }
    
    if(dfn[u] == low[u]) {
        cluster++;
        int hd;
        do {
            hd = st[top--];
            instack[hd] = false;
            belong[hd] = cluster;
        }
        while(hd != u);
    }
}

(PS:一道经典的求强连通分量的题 Networks of School

拓扑排序

在图论中，我们经常讨论有向无环图DAG（Directed Acyclic Graph），这类图常用来描述节点之间的依赖关系（先修课程、软件包的安装依赖）。对于DAG，我们可以对其进行拓扑排序。
一个DAG的拓扑排序是图中所有顶点的一个排列：v1, v2, ..., vn，对于原图中每条边(vi, vj)都有i < j。下图就展示了一个拓扑排序的例子：

topological.png

拓扑排序可以通过一个很直观的策略求得：选取当前所有入度为0的点，把它们加入拓扑序列中，再把这些点的出边删去，反复这两个操作，直到所有的点都加入拓扑序列中。对应的C++实现如下：

std::vector<int> topsort(const std::vector<std::vector<int> > &g) {
    int n = g.size();
    std::vector<int> d(n);
    for(int i = 0; i < n; i++)
        for(int j = 0; j < g[i].size(); j++)
            d[g[i][j]]++;
    
    std::queue<int> q;
    std::vector<int> seq;
    for(int i = 0; i < n; i++)
        if(!d[i]) q.push(i);
    while(!q.empty()) {
        int hd = q.front();
        q.pop();
        seq.push_back(hd);
        for(int i = 0; i < g[hd].size(); i++) {
            int dst = g[hd][i];
            d[dst]--;
            if(!d[dst]) q.push(dst);
        }
    }
    return seq;
}

正确性证明：
结论1：算法一定会终结。队列中最多会压入n个顶点，每次循环都会取出第一个元素，因此最多循环n次，同时，每次循环内会访问当前队列第一个点的所有出边，这个点不会再加入队列，因此每条边最多被访问一次，算法总的复杂度O(m+n)。
结论2：对于连通的DAG，算法一定会返回一个长度为n的序列。如果当前序列长度不足n，说明连通图中还有点没有被加入序列，而此时如果队列为空，则说明没有入度为0的点了，这在无环图是不可能的。这同时提醒我们，对于没有保证连通性的图，需要多次的拓扑排序已确保每个连通分量中的点都加入了序列。同时，如果考虑所有连通分量后，最终返回序列的长度小于n，那么说明原图中有环。
结论3：对于返回的序列v1, v2, ..., vn，原图中不存在边(vi, vj)使得i > j。假如有这样一条边从vi指向vj，且在拓扑序列中vj在vi之前。算法中vj在被删除时，vi还没被删除，因此vj的入度不会为0，矛盾！

(PS:一道不错的拓扑排序的题 All Discs Considered

附

本文图片来自 Lecture Slides for Alogorithm Design by Jon Kleinberg and Éva Tardos.