强连通分量¶
若一张有向图的节点两两互相可达，则称这张图是强连通的。
那么实际上我们发现找强连通分量就是在有向图上找环。我们可以大致考虑如下步骤：
-
在有向图上dfs，同时维护一个存有已访问点的栈。
-
对于已访问的点打上特殊的标记，表示该点是之前访问过的（称为0标记），还是当前路径中走过的（称为1标记）。
-
当重新走到一个含有1标记的节点上时，说明发现一个环，从栈中取出环上的节点。
tarjan 算法介绍¶
算法目的:
Tarjan 算法是基于***深度优先搜索***的算法，用于求解图的连通性问题。Tarjan 算法可以在线性时间内求出无向图的割点与桥，进一步地可以求解无向图的双连通分量；同时，也可以求解有向图的强连通分量、必经点与必经边。
如果你对上面的一些术语不是很了解，没关系，我们只要知道 Tarjan 算法是基于深度优先搜索的，用于求解图的连通性问题的算法 就好了。
强连通：若一张有向图的节点两两互相可达，则称这张图是强连通的。 强连通分量（Strongly Connected Components，SCC）：极大的强连通子图。例如，图中的SCC: (1) 1,2,3,4,9 (2) 5,6,8 (3) 7 对图深搜时，每一个节点只访问一次，被访问过的节点与边构成**搜索树**。
强连通分量¶
一个环是强连通分量。一个没有出边的点也是强连通分量。
如果一个子图可以构成多个连通分量，则只有包含节点最多的才是强连通分量。（如下图4，包含3个节点的环不是强连通分量，4个的才是 ）一个图中的强连通分量可以有多个，并且他们所包含的节点数可能不同（如上图1,2,3,4,9和5,6,8和7）
分类之后，就可以通过不同的边寻找环，从而找到强连通分量
如果节点x是某个强连通分量在搜索树中遇到的第一个节点，那么这个强连通分量的其余节点肯定是在搜索树中以x为根的子树中。节点x被称为这个强连通分量的根。
Tarjan算法¶
下面是图片中的文本内容，已经将数学公式和变量转换为了 LaTeX 格式：
Tarjan（塔扬）算法
-
时间戳 dfn[x]：节点 x 第一次被访问的顺序。
-
追溯值 low[x]：从节点 x 出发，所能访问到的最早时间戳。
入x时，盖戳、入栈。 枚举 x 的邻点 y，分三种情况。
(1) 若 y 尚未访问：对 y 深搜。回 x 时，用 low[y] 更新 low[x]。因为 x 是 y 的父节点，y 能访问到的点，x 一定也能访问到。 (2) 若 y 已访问且在栈中：说明 y 是祖先节点或左子树节点，用 dfn[y] 更新 low[x]。 (3) 若 y 已访问且不在栈中：说明 y 已搜索完毕，其所在连通分量已被处理，所以不用对其做操作。
离 x 时，记录 SCC。只有遍历完一个 SCC，才可以出栈。更新 low 值的意义：避免 SCC 的节点提前出栈。
1.入x¶
//入x时,时间戳追溯值更新,入栈
dfn[x]=low[x]=++tot;
stk[++top]=x;instk[x]=1;
2.找x¶
枚举x的邻点y，可能会有3种情况
for(int i=0;i<e[x].size();i++){//枚举x的邻点y
int y=e[x][i];
if(!dfn[y]){//如果y还没有访问过
tarjan(y);//向下走
low[x]=min(low[x],low[y]);//返回时更新
}
}
1.没有访问过y
考察以下走法
1→2→3→1
节点3可以访问到dfn最小的节点为1，dfn为1.并且节点3是从1，2走过来的，说明1，2也可以通过节点3访问到dfn最小的节点为1，因此在返回时要更新low为自己的和邻点的low的最小值
向下继续走
if(!dfn[y]){//如果y还没有访问过
tarjan(y);//向下走
low[x]=mid(low[x],low[y]);//返回时更新
}
2.y被访问过
考察点3.它可以走到点1（一个**被访问过的点**）
考察点9.它可以走到点3（一个被访问过的点）也是同理
不用往回走（即不需要tarjan(y);）
else if(dfn[y]&&instk[y]){//说明 y被访问过 ->要么y是祖先(在x出通过返祖边访问到了),要么是左子树的点(在x通过横插边访问到了)
low[x]=min(low[x],dfn[y]);
}
3.y被访问过并且已经弹出栈
只有当一个强连通分量全部扫描完，才会将节点弹出。如果y已经被弹出了，说明y所在的强连通分量已经被扫描完了。又因为一个点所在的强连通分量**有且只有一个**，所以y一定不是目前正在扫描的强连通分量里的一个点，直接忽略它
离x¶
if(dfn[x]==low[x]){//说明x是这个强连通分量的根
int y;++cnt;
do{
y=stk[top--];instk[y]=0;
scc[y]=cnt;
++siz[cnt];
} while(y!=x);
}
考察以下图
当访问了5→6→8，访问到5（通过返祖边），此时属于**2.y被访问过情况，执行**low[x]=min(low[x],dfn[y]);
并且从8不能继续走到5，也没有其他出边（7属于**3.y被访问过并且已经弹出栈情况，忽略**）
开始回溯
将点8，6，5的low更新为min(low[8],dfn[5])即dfn[5]。当回溯到5时，把low[5]也更新为了dfn[5]，并且5的所有邻点都访问完了（7忽略，理由同上）。此时节点5的**for循环**结束，运行到判定环节（离x）。也恰好满足(dfn[x]==low[x])说明x是这个强连通分量的根
此时栈里有...,5,6,8
执行循环，不断出栈，直到把5的scc更新后，发现x=y（y就是目前的栈顶，5），就说明这个强连通分量走完了
代码¶
/*////////ACACACACACACAC///////////
Code By Ntsc
/*////////ACACACACACACAC///////////
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N=1e5;
vector<int> e[N];//邻接矩阵
int dfn[N],low[N],tot;//时间戳，追溯值，给时间戳编号的计数器
int stk[N],top;//栈，指针
bool instk[N]; //是否在栈中
int scc[N],siz[N],cnt; //记录每个点在那个强连通分量里, 每个点所在的强连通分量的大小,强连通分量的数量
int ans;
void tarjan(int x){//从节点x进入
if(scc[x])return;//如果已经是某个强连通分量里的点,停止函数
//入x时,时间戳追溯值更新,入栈
dfn[x]=low[x]=++tot;
stk[++top]=x;instk[x]=1;
for(int i=0;i<e[x].size();i++){//枚举x的邻点y
int y=e[x][i];
if(!dfn[y]){//如果y还没有访问过
tarjan(y);//向下走
low[x]=min(low[x],low[y]);//返回时更新
}else if(dfn[y]&&instk[y]){//说明 y被访问过 ->要么y是祖先(在x出通过返祖边访问到了),要么是左子树的点(在x通过横插边访问到了)
low[x]=min(low[x],dfn[y]);
}
}
if(dfn[x]==low[x]){//说明x是这个强连通分量的根
int y;++cnt;
int flag=0;//记录当前强连通分量点的个数
do{
flag++;
y=stk[top--];instk[y]=0;
// ans-=e[y].size();
scc[y]=cnt;
++siz[cnt];
} while(y!=x);
if(flag>1)ans++;
}
}
signed main(){
int m,n;
cin>>n>>m;
for(int i=1;i<=m;i++){
int a,b;
cin>>a>>b;
e[a].push_back(b);
}
// ans=m;
for(int i=1;i<=n;i++)tarjan(i);//图可能不连通！
// for(int i=1;i<=n;i++)cout<<scc[i]<<' ';
cout<<ans;
return 0;
}
注意本代码与下面例题代码有一点不同，下面的代码不能计算点数为1的强连通分量，但本代码可以，只需要修改if(flag>1)ans++;即可。
例题 #1 [USACO06JAN]The Cow Prom S¶
有一个 \(n\) 个点，\(m\) 条边的有向图，请求出这个图点数大于 \(1\) 的强联通分量个数。
对于全部的测试点，保证 \(2\le n \le 10^4\)，\(2\le m\le 5\times 10^4\)，\(1 \leq a, b \leq n\)。
完整代码
/*////////ACACACACACACAC///////////
Code By Ntsc
/*////////ACACACACACACAC///////////
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N=1e5;
vector<int> e[N];//邻接矩阵
int dfn[N],low[N],tot;//时间戳，追溯值，给时间戳编号的计数器
int stk[N],top;//栈，指针
bool instk[N]; //是否在栈中
int scc[N],siz[N],cnt; //记录每个点在那个强连通分量里, 每个点所在的强连通分量的大小,强连通分量的数量
int ans;
void tarjan(int x){//从节点x进入
//入x时,时间戳追溯值更新,入栈
dfn[x]=low[x]=++tot;
stk[++top]=x;instk[x]=1;
for(int i=0;i<e[x].size();i++){//枚举x的邻点y
int y=e[x][i];
if(!dfn[y]){//如果y还没有访问过
tarjan(y);//向下走
low[x]=min(low[x],low[y]);//返回时更新
}else if(dfn[y]&&instk[y]){//说明 y被访问过 ->要么y是祖先(在x出通过返祖边访问到了),要么是左子树的点(在x通过横插边访问到了)
low[x]=min(low[x],dfn[y]);
}
}
if(dfn[x]==low[x]){//说明x是这个强连通分量的根
int y;++cnt;
int flag=0;
do{
flag++;
y=stk[top--];instk[y]=0;
scc[y]=cnt;
++siz[cnt];
} while(y!=x);
if(flag>1)ans++;
}
}
signed main(){
int m,n;
cin>>n>>m;
for(int i=1;i<=m;i++){
int a,b;
cin>>a>>b;
e[a].push_back(b);
}
for(int i=1;i<=n;i++)if(!dfn[i])tarjan(i);//图可能不连通！但也不要重复扫描！
cout<<ans;
return 0;
}
我们也可以tarjan完了之后统一统计，去掉flag
在输出答案前统计答案，在输出答案前插入以下代码
for(int i=1;i<=cnt;i++)
if(siz[i]>1) ans++;
融会贯通：dfn与low替换¶
在边双连通分量和强连通分量中，我们发现下面两种写法是等效的。
if(i!=(eid^1)) low[u]=min(low[u],dfn[v]);
//等于
if(i!=(eid^1)) low[u]=min(low[u],low[v]);
但是在点双连通分量中，这样写是错误的，这是为什么呢？
因为在点双连通分量中，一个点可能在两个点双连通分量中，我们在更新点\(u\)的\(low_v\)时，用到的\(v\)是与\(u\)属于同一个点双连通分量里的，但可能在前面的某个也包含点v的点双连通分量中已经更新过其\(low_v\)了，这样的话就可能跨不同的点双连通分量访问\(low_v\)了，这样的话就错了。
而在边双连通分量中，该边要么不属于任何边双连通分量，要么一定只属于一个边双连通分量（因为如果该边属于若干个边双连通分量，首先保证其为广义双向边，但如果两个边双连通分量有一个公共的广义双向边，那么这两个边双连通分量其实是一个整体（即它们就是一个边双连通分量））
强连通分量标号和拓扑序的关系¶
拓扑序（Topological Order）是指对有向无环图（DAG）中的顶点进行线性排序，使得对于每一条有向边(u, v)，u在排序中都出现在v之前。只有有向无环图才能进行拓扑排序。
在有向图中，强连通分量的标号顺序与拓扑序的关系如下：
-
Tarjan算法给出的强连通分量的标号顺序并不是拓扑序，因为强连通分量本身可能包含环，因此不能简单地映射到一个线性的拓扑序。
-
Tarjan算法在处理过程中，实际上是按照某种“逆拓扑序”来发现强连通分量的，这是因为算法在深度优先搜索（DFS）的过程中会先访问那些没有出边的节点，而这与拓扑排序的过程是相反的。
-
如果我们将图中的所有强连通分量缩成单个节点，那么在这些缩点后的节点形成的DAG中进行拓扑排序，得到的顺序将与Tarjan算法给出的强连通分量的标号顺序相反。
因此，可以说，在缩点后的DAG中，强连通分量（缩点后）的标号顺序是其拓扑序的逆序。但要注意的是，这种说法仅在考虑了强连通分量之间的依赖关系（即从一个强连通分量到另一个强连通分量的有向边）时才成立。单个强连通分量内部的节点由于存在环，所以内部并不满足拓扑序的定义。