强连通分量（SCC）

如果一个有向图G不是强连通图，那么可以把它分成多个子图，其中每个子图的内部是强连通的，而且这些子图已经扩展到最大，不能与子图外的任意点强连通，称这样的一个“极大强连通”子图是G的一个强连通分量。

Kosaraju算法

时间复杂度 O(N+E)

Kosaraju 算法用到了“反图”的技术，基于下面两个原理：
（1）一个有向图G，把G所有的边反向，建立反图rG，反图rG不会改变原图G的强连通行。也就是说，图G的SCC数量与rG的SCC数量相同。
（2）对原图G和反图rG各做一次DFS，可以确定SCC的数量。

算法步骤：

在G上做一次DFS，标记点的先后顺序。在DFS的过程中标记所有经过的点，把递归到最底层的那个点标记为最小，然后在退回的过程中，其他点的标记逐个递增。
在返图rG上再做一次DFS，顺序从标记最大的点开始到最小的点。记录它能达到的点，这些点组成一个SCC，删除该SCC中所有点，从剩下的最大的点继续DFS寻找下一个SCC，依次循环找到所有的SCC。

注：把只有出度的点排在前面，只有入度的点排在后面，在反图中排在前面的点出不去，排在后面的点能出去的点已被删除，只有强连通分量依然可以互通。

代码：

//hdu-1269 http://acm.hdu.edu.cn/showproblem.php?pid=1269
#include<bits/stdc++.h>

using namespace std;

const int maxn = 1e4+1;

vector<int> g[maxn], rg[maxn];
int vis[maxn], scc[maxn], cnt;
vector<int> st; // 模拟栈标记点的顺序

void dfs(int x) {
    if (vis[x]) return ;
    vis[x] = 1;
    for(auto to: g[x]) dfs(to);
    st.push_back(x);
}

void rdfs(int x) {
    if (scc[x]) return ;
    scc[x] = cnt;
    for(auto to: rg[x]) rdfs(to);
}

void Kosaraju(int n) {
    cnt = 0;
    st.clear();
    for(int i = 1; i <= n; ++ i) {
        vis[i] = scc[i] = 0;
    }
    for(int i = 1; i <= n; ++ i) dfs(i);
    for(int i = n-1; i >= 0; -- i) {
        if (!scc[st[i]]) {++cnt; rdfs(st[i]);}
    }
}

int main() {
    int n, m; while(scanf("%d%d", &n, &m), n != 0 || m != 0) {
        for(int i = 1; i <= n; ++ i) {
            g[i].clear();
            rg[i].clear();
        }
        for(int i = 1; i <= m; ++ i) {
            int u, v; scanf("%d%d", &u, &v);
            g[u].push_back(v);
            rg[v].push_back(u);
        }
        Kosaraju(n);
        printf("%s\n", cnt == 1 ? "Yes" : "No");
    }
    return 0;
}

Tarjan算法

时间复杂度 O(N+E)

上面的 Kosaraju 算法，其做法是从图中一个一个地把 SCC “挖”出来。Tarjin 算法能在一次 DFS 中把所有点按 SCC 分开。这并不是不可思议的，它利用的了 SCC 的如下特征：
定理10.3：一个 SCC，从其中任何一个点出发，都至少有一条路劲能绕回到自己。

算法步骤：
以上图为例，其中有3个 SCC，即 A、E、F。假设从 F 中的一个点开始 DFS。DFS过程可能会中途跳出F，转入 A 或者 E，总之最后会进入一个 SCC。

假设 DFS 过程是 $F \rightarrow E \rightarrow A$ ，最后进入 A。
从 F 开始递归搜索，访问到的某些点进入栈。
E 点中的某些点进入栈。
在 DFS 的最底层，A 的所有点将被被访问到并进入栈，当前栈顶的几个元素就是 A 的点，标记为同一个 SCC ，并弹出栈。
DFS 回到 E，在 E 中完成所有点的搜索并且入栈，当前栈顶的几个元素就是 E 的点，标记为同一个 SCC，并弹出栈。
回到 F，完成 F 的所有点的搜索并且入栈，当前栈顶的几个元素就是 F 的点，标记为同一个 SCC，并弹出栈。

注：dfn[ ] 表示节点的被访问时间，low[ ] 表示该点祖先节点的访问时间，当某点遇到已访问的节点且该节点就在栈内(或不在缩点（SCC）内)，则该点更新 low[ ]，并向前更新 low[ ] 到祖先节点为止。

//hdu-1269 http://acm.hdu.edu.cn/showproblem.php?pid=1269
#include<bits/stdc++.h>

using namespace std;

const int maxn = 1e4+1;

vector<int> g[maxn];
// dfn 表示时间， low 表示SCC祖先
int dfn[maxn], low[maxn], cnt;
int scc[maxn], tot; // 统计 SCC
int st[maxn], top; // 模拟栈

void dfs(int x) {
    dfn[x] = low[x] = ++cnt;
    st[top++] = x;
    for(auto to: g[x]) {
        if (!dfn[to]) {
            dfs(to);
            low[x] = min(low[x], low[to]);
        }
        else if (!scc[to])
            low[x] = min(low[x], dfn[to]);
    }
    if (dfn[x] == low[x]) {
        ++ tot;
        while(1) {
            int y = st[--top];
            scc[y] = tot;
            if (x == y) break;
        }
    }
}

void Tarjin(int n) {
    tot = cnt = top = 0;
    for(int i = 1; i <= n; ++ i) {
        dfn[i] = low[i] = scc[i] = 0;
    }
    for(int i = 1; i <= n; ++ i) {
        if (!dfn[i]) dfs(i);
    }
}

int main() {
    int n, m; while(scanf("%d%d", &n, &m), n != 0 || m != 0) {
        for(int i = 1; i <= n; ++ i) {
            g[i].clear();
        }
        for(int i = 1; i <= m; ++ i) {
            int u, v; scanf("%d%d", &u, &v);
            g[u].push_back(v);
        }
        Tarjin(n);
        printf("%s\n", tot == 1 ? "Yes" : "No");
    }
    return 0;
}

Garbow算法

时间复杂度 O(N+E)
Tarjan算法和Garbow算法是同一个思想的不同实现，Garbow 算法多维护了一个栈来代替low[ ]，不用频繁更新low[ ]，所以速度快了一点。

//hdu-1269 http://acm.hdu.edu.cn/showproblem.php?pid=1269
#include<bits/stdc++.h>

using namespace std;

const int maxn = 1e4+1;

vector<int> g[maxn];
int dfn[maxn], tot;
int scc[maxn], cnt; // 统计 SCC
int st[maxn], top, st2[maxn], top2; // 模拟栈

void dfs(int x) {
    dfn[x] = ++tot;
    st[top++] = st2[++top2] = x;
    for(auto to: g[x]) {
        if (!dfn[to]) dfs(to);
        else if (!scc[to]) // 不在缩点内 遇到必在栈内
            while(dfn[st2[top2]] > dfn[to]) top2--;
    }
    if (st2[top2] == x) {
        ++ cnt;
        while(1) {
            int y = st[--top];
            scc[y] = cnt;
            if (x == y) break;
        }
        top2 --;
    }
}

void Garbow(int n) {
    tot = cnt = top = 0;
    for(int i = 1; i <= n; ++ i) {
        dfn[i] = scc[i] = 0;
    }
    for(int i = 1; i <= n; ++ i) {
        if (!dfn[i]) dfs(i);
    }
}

int main() {
    int n, m; while(scanf("%d%d", &n, &m), n != 0 || m != 0) {
        for(int i = 1; i <= n; ++ i) {
            g[i].clear();
        }
        for(int i = 1; i <= m; ++ i) {
            int u, v; scanf("%d%d", &u, &v);
            g[u].push_back(v);
        }
        Garbow(n);
        printf("%s\n", cnt == 1 ? "Yes" : "No");
    }
    return 0;
}

有向图的连通性

强连通分量（SCC）

Kosaraju算法

Tarjan算法

Garbow算法