相关概念：
连通图：在无向图中，如果图G中任意两个节点都是连通的，则称图G为连通图。
连通分量：无向图G的极大连通子图称为图的连通分量。连通分量可能不止一个，对每个连通分量，如果再向其中加入一个节点，这个子图就不连通。
下图中有几个连通分量？
draw.io
答案：
有3个连通分量，如下图所示，通过不同颜色标记：
draw.io
强连通图：在有向图中，如果图中任意两个节点从u到v都有路径，且从v到u也有路径，则称图G为强连通图。
强连通分量：有向图G的极大强连通子图被称为图G的强连通分量。强连通分量也不止一个，对每个强连通分量，如果再向其中加入一个节点，这个子图就不是强连通图。
下图中有几个强连通分量？
draw.io
答案：
有3个强连通分量，如下图所示，通过不同颜色标记：
draw.io
强连通分量求解算法-Tarjan算法模板：
#define MAXN 1005
int G[MAXN][MAXN]; // 邻接矩阵
int n; // 顶点数，顶点编号从0开始
int timestamp; // 时间戳
int dfn[MAXN]; // 第一次遍历到达u的时间戳，至少为1，为0表示u还未被访问过
int low[MAXN]; // 从顶点u开始的DFS遍历能到达的最小时间戳
stack<int> stk;
bool in_stk[MAXN]; // 记录顶点u是否在栈中
int scc_cnt; // 记录强连通分量的个数，也用于给强连通分量编号
int id[MAXN]; // 记录顶点所属的强连通分量编号
void tarjan_dfs(int u) {
dfn[u] = low[u] = ++timestamp; // 第一次遍历到u，初始化当前点的时间戳
stk.push(u);
in_stk[u] = true;
for(int i = 0; i < n; i++) { // 遍历所有u能到的邻接点
if(G[u][i]) {
if(dfn[i] == 0) { // 如果这个点还没被访问过
tarjan_dfs(i); // 遍历邻接点
low[u] = min(low[u], low[i]); // 子结点能到的最小时间戳u能也到
} else if(in_stk[i]) { // 如果这个点还在栈中，说明这个点比u点先访问到，它的时间戳也应该更早
low[u] = min(low[u], dfn[i]); // 用层级更高的点的时间戳更新u的low值
}
}
}
if(dfn[u] = low[u]) { // 如果u为某个强连通分量的最高点，则可以输出这个强连通分量
scc_cnt++; // 连通分量数加1
int tmp;
do {
tmp = stk.top();
stk.pop();
in_stk[tmp] = false;
id[tmp] = scc_cnt; // 标记这个点属于哪个强连通分量
} while(tmp != u);
}
}
void tarjan() {
for(int i = 0; i < n; i++) { // 对所有点进行强连通分量计算
if(dfn[i] == 0) {
tarjan_dfs(i);
}
}
}
算法大概思路：
- DFS遍历所有节点，对每个节点，先访问其全部的邻接点，再访问节点内容。
- 记录时间戳，从1开始，按DFS遍历的顺序，每个节点的时间戳依次递增，记为
dfn[u]。 每次访问完一个节点的全部邻接点后，记录从这个节点开始DFS遍历能找到的最小时间戳，记为
low[u]。dfn[u]：表示第一次遍历到u的时间戳。low[u]：表示从点u开始DFS遍历能到达的最小时间戳。- 如果有
dfn[u] == low[u]，则说明u是所在强连通分量的最高点，可以把这个强连通分量找出来。
参考链接：
[算法]轻松掌握tarjan强连通分量p1_什么是强连通分量 - YouTube
[算法]轻松掌握tarjan强连通分量p2_两种dfs遍历 - YouTube
[算法]轻松掌握tarjan强连通分量p3_一个简单例子理解算法 - YouTube
[算法]轻松掌握tarjan强连通分量p4 更完整的例子 - YouTube
[算法]轻松掌握tarjan强连通分量p5_code实现 - YouTube