利用 Tarjan 求强连通分量（SCC）

强连通与强连通分量（SCC）

首先需要知道它们的定义……

强连通：有向图中两个点可以相互到达，那么它们就是强连通的。

强连通分量：有向图中的一组点可以相互到达（就是多个点可以相互到达）

缩点：把强连通分量看成是一个大点，保留那些不在强连通分量里的边，这样的图就是缩点后的图。
就像这样

Tarjan 算法

下面引入正题：Tarjan 算法求强连通分量。

利用 DFS，我们定义每个的两个参数，一个是 dfn，表示这个点是第几个被搜索到（即时间戳），还有一个是 low，表示搜索树中最小子树的根（嗯，不理解不要紧，下面这张图说明了一切）

比如对于这个图来说

算法描述

我们使用栈来存储强连通分量，如果这个点没有 dfn 值（即 dfn 值为初始值），就把它加入栈。
如果这个点有出边，就继续找下去，一直找到没有出边或是子节点被访问过（即该有 dfn 值）为止。
如果子节点在栈内，那么就更新当前点的 low 值，使之等于这个子节点的 dfn 值（也可以是 low 值，但建议用 dfn 值。求割点时也用到相似的 Tarjan 算法，但是只能用 dfn 值）。
在回溯的过程中，比较当前点的 low 值与其子节点的 low 值，更新当前点的 low 值为更小的那个。
如果当前点的 low = dfn，说明这是一个强连通分量的根节点，那么就出栈（此时出栈的是同一个强连通分量里的点）直到这个点（即根节点）出栈为止。

在实际的程序中，我们需要枚举每一个点，如果这个点没有 dfn 值（没有被访问过），就进行以上算法，以保证每一个点都被访问过。

算法进行后的搜索树长这样

分步模拟

还是上面那张图

把 1 入栈，vis 表示节点是否在栈内

找到 1 的子节点 2，并把它入栈

找到 2 的子节点 4，入栈。
找到 4 的子节点 1，发现它被访问过且在栈内，那么更新 low[4] 的值为 dfn[1] = 1

找到 4 的子节点 6，入栈。而 6 没有出边，进行回溯。

发现 low[6] = dfn[6] = 4，故把 6 出栈。那么 6 就是一个强连通分量（只有一个点的强连通分量，太孤独了）

4 已经没有可以继续进行枚举的出边了，回溯。
回溯到 2 时，发现 low[2] = 2 > low[4] = 1，故更新 low[2] 的值为 1。

回溯到 1，找到 1 的另一个子节点 3，入栈。
发现 3 的子节点 4 被访问过且在栈内，更新 low[3] 的值为 dfn[4] = 3。

找到 3 的子节点 5，入栈。而 5 的子节点 6 被访问过且不在栈内，回溯。

发现 low[5] = dfn[5] = 6，故把 5 出栈。此时 5 也是一个孤独的强连通分量。

一直回溯到 1，此时 low[1] = dfn[1] = 1，故出栈直到 1 出栈为止。

此时图中所有的点都访问过，这样所有的强连通分量已经找到。

代码

#include <bits/stdc++.h>
using namespace std;
const int maxN = 5e5 + 3;
struct Edge {
    int next, to;
} edge[maxN];
int head[maxN], dfn[maxN], low[maxN];
bool vis[maxN];
int cnt, tot, n, m;
stack<int> sta;
template<typename Tp> void read(Tp &x) {
    char c = getchar();
    x = 0;
    while (!isdigit(c)) c = getchar();
    do {
        x = x * 10 + (c ^ 48);
        c = getchar();
    } while (isdigit(c));
}
void add(int from, int to) {
    edge[++cnt].next = head[from];
    edge[cnt].to = to;
    head[from] = cnt;
}
void tarjan(int v) {
    dfn[v] = low[v] = ++tot;
    sta.push(v);
    vis[v] = true;
    for (int i = head[v]; ~i; i = edge[i].next) {
        int u = edge[i].to;
        if (!dfn[u]) {
            tarjan(u);
            low[v] = min(low[v], low[u]);
        } else if (vis[u])
            low[v] = min(low[v], dfn[u]);
    }
    if (dfn[v] == low[v]) {
        int u = sta.top();
        do {
            u = sta.top();
            printf("%d ", u);
            vis[u] = false;
            sta.pop();
        } while (v != u);
        printf("\n");
    }
}
int main() {
    memset(head, -1, sizeof(head));
    read(n), read(m);
    for (int i = 1; i <= m; i++) {
        int from, to;
        read(from), read(to);
        add(from, to);
    }
    for (int i = 1; i <= n; i++)
        if (!dfn[i]) tarjan(i);
}

输入

6 8
1 3
1 2
2 4
3 4
3 5
4 6
4 1
5 6

输出

6
5
3 4 2 1

缩点

怎么进行缩点？Tarjan 算法已经帮你把所有的强连通分量找出来了！
把上面的代码稍微改动一些就好了！

if (dfn[v] == low[v]) {
    sccnt++; // 每找到一个强连通分量，强连通分量序号 +1
    int u = sta.top();
    do {
        u = sta.top();
        vis[u] = false;
        sta.pop();
        color[u] = sccnt; // color 数组存储每个点所在的 SCC 序号，类似于染上相同的颜色
    } while (v != u);
}

更详细的见这篇文章

说明

求强连通分量还有 Kosaraju 算法，利用正反 DFS。在此不再赘述。
在题目中，SCC 一般要缩点，与拓扑排序和 DP 结合。