一、基本概念
强连通图（Strongly Connected Graph）是指在有向图G中，如果对于每一对vi、vj，vi≠vj，从vi到vj和从vj到vi都存在路径，则称G是强连通图。
有向图中的极大强连通子图称做有向图的强连通分量。
连通分量：对于图G来的一个子图中，任意两个点都可以彼此到达，这个子图就被称为图G的连通分量（一个点就是最小的连通分量）
最大连通分量：对于图G的一个子图，这个子图为图G的连通分量，且是图G所有连通分量中包含节点数最多的那个，即为G的最大联通分量
时间戳：搜索时第几个搜索到这个点。
二、定理
定理：一个有向图G是强连通的，当且仅当G中有一个回路，它至少包含每个节点一次。
证明：
（1）充分性：如果G中有一个回路，它至少包含每个节点一次，则G中任两个节点都是互相可达的，故G是强连通图。
（2）必要性：如果有向图是强连通的，则任两个节点都是相互可达。故必可做一回路经过图中所有各点。若不然则必有一回路不包含某一结点v，并且v与回路上的个节点就不是相互可达，与强连通条件矛盾 。
三、算法
（1）Tarjan 算法
思想：
low，dfn。dfn表示这个点的时间戳，而low代表这个点所能到达的最小的时间戳，开始low都等于dfn，但会经过不断更新而减少。
从1节点进行深度优先搜索，途中用树（一个转化为栈的树）维护。
当遇到一个点时，有如下判断：
1、如果这个点没有访问过，就将这个点加入树（栈）
2、如果这个点访问过，且在树（栈）里，与这个点的low比较，更新自己的low
返回时更新low
当一个点遍历所有的边后这个点的low还是等于dfn，将个点及以上出栈，这个点及栈以上的点构成一个连通分量。
伪代码：
void tarjan(int 当前点)
{
这个点的low=dfn=时间戳;
将这个点入栈;
标记这个点入栈;
枚举这个点连接的所有边
{
如果目标点没有被访问过
{
tarjan(目标点);
更新当前点的low;
}
如果目标点被访问过
{
更新当前点的low;
}
}
如果当前点的low==dfn
{
将这个点及栈以上的点出栈，标记成一个强连通分量;
ans++;
}
} C++版本一
//in:时间戳下标
//dfn[i]:i节点的时间戳
//low[i]:i所能到达的最小的时间戳
//vis[i]:i是否在栈里
//head[i],next[i],to[i]:邻接表
void tarjan(int u)
{
in++;
dfn[u]=in;
low[u]=in;
S.push(u);
vis[u]=1;
for(int e=head[u];e;e=next[e])
{
if(!dfn[to[e]])
{
tarjan(to[e]);
low[u]=min(low[to[e]],low[u]);
}
else if(vis[to[e]])
low[u]=min(low[u],dfn[to[e]]);
}
if(low[u]==dfn[u])
{
while(!S.empty() && S.top()!=u)
{
vis[S.top()]=0;
S.pop();
}
vis[u]=0;
S.pop();
ans++;
}
}
（2）Korasaju 算法
四、例题
https://www.luogu.org/problemnew/show/P1726（题解：https://blog.csdn.net/weixin_43272781/article/details/89790404）
京公网安备 11010502036488号