-
强连通分量
强连通：若一张有向图的节点两两之间可以互相抵达，那么这一张图是强连通的。
强连通分量：极大的强连通子图。
对图深度搜索的时候，每一个节点只访问一次，被访问过的节点与边构成搜索树。
有向边按照访问的情况可以分为如下4类：
1. 树边：访问节点走过的边。
2. 返祖边：指向祖先节点的边。
3. 横叉边：右子树指向左子树的边。
4. 前向边：指向子树中节点的边。
返祖边与树边一定构成环，横叉边可能与树边构成环，前向边没有用。
如果节点 \(x\) 是某个强连通分量在搜索树中遇到的第一个节点，那么这个强连通分量的其余节点肯定是在搜索树中以 \(x\) 为根的子树中。节点 \(x\) 被称为这个强连通分量的根。
-
Tarjan算法
例题
原理
定义
时间戳 dfn[x]：节点 \(x\) 第一次被访问的顺序
追溯值 low[x]：节点 \(x\) 能访问到时间戳最小的值
对能够访问的定义：（以下两个条件满足其一即可）
-
以 \(x\) 为根的搜索树的所有节点（实际上以 \(x\) 为根的搜索树的子节点的时间戳一定大于 \(x\) 的时间戳）
-
通过一条非搜索树（返祖边与横叉边）上的边，能够到达搜索树的所有节点
搜索过程
-
开始搜索节点 \(x\) 时，对 \(x\) 盖上时间戳并入栈
-
枚举 \(x\) 的相邻顶点 \(y\) ，分三种情况：
若 \(y\) 没有被访问过，那么对 \(y\) 深度搜索。在重新访问到 \(x\) 的时候，用
low[y]更新low[x]。这是因为 \(x\) 是 \(y\) 的父节点，只要 \(y\) 能够访问到，那么x也一定能访问到。若y已经访问且在栈中：说明 \(y\) 是祖先节点或者左子树节点，那么用
dfn[n]更新low[x]。若y已访问且不在栈中，说明 \(y\) 已经搜索完毕，因为其连通分量已被处理，所以不用对其做操作。
-
对节点 \(x\) 搜索完毕时，记录这个极大强连通子图。只有遍历完第一个极大强连通子图，才可以出栈。更新
low[x]值的意义：避免极大强连通子图的节点提前出栈.
代码
//洛谷P2683 The Cow Prom S
//tarjan算法
#include <iostream>
#include <vector>
using namespace std;
const int N = 10005;
vector<int>e[N];//存边
int dfn[N], low[N], tot;//时间戳，追溯值，时间戳的编号
int stk[N], instk[N], top;//栈，是否在栈中，栈指针
int scc[N], siz[N], cnt;//记录某个点在哪个强连通分量中，某个强连通分量的点数，强连通分量的编号
int n, m;//n个点，m条边
int ans = 0;
void tarjan(int x)
{
//开始搜索x
dfn[x] = low[x] = ++tot;
stk[++top] = x, instk[x] = 1;
for (int y : e[x])
{
if (!dfn[y])
{//如果y尚未被访问
tarjan(y);
low[x] = min(low[x], low[y]);//回x的时候更新low
}
else if (instk[y])
{//若y已经被访问且在栈中
low[x] = min(low[x], dfn[y]);//更新low
}
}
//结束搜索x
if(dfn[x]==low[x])
{
int y;
cnt++;
while (1)
{
y = stk[top--];
instk[y] = 0;
scc[y] = cnt;//记录y隶属于哪一个强连通分量
++siz[cnt];//记录这个强连通分量的大小
if (y == x)break;
}
}
}
void init()
{
cin >> n >> m;
for (int i = 1; i <= m; i++)
{
int u, v;
cin >> u >> v;
e[u].push_back(v);
}
}
int main()
{
init();
for (int i = 1; i <= n; i++)if (!dfn[i])tarjan(i);
for (int i = 1; i <= cnt; i++)if (siz[i] > 1)ans++;
cout << ans << endl;
return 0;
}