• 强连通分量

强连通：若一张有向图的节点两两之间可以互相抵达，那么这一张图是强连通的。

强连通分量：极大的强连通子图。

对图深度搜索的时候，每一个节点只访问一次，被访问过的节点与边构成搜索树。

有向边按照访问的情况可以分为如下4类：

1. 树边：访问节点走过的边。

2. 返祖边：指向祖先节点的边。

3. 横叉边：右子树指向左子树的边。

4. 前向边：指向子树中节点的边。

返祖边与树边一定构成环，横叉边可能与树边构成环，前向边没有用。

如果节点 \(x\) 是某个强连通分量在搜索树中遇到的第一个节点，那么这个强连通分量的其余节点肯定是在搜索树中以 \(x\) 为根的子树中。节点 \(x\) 被称为这个强连通分量的根。

• Tarjan算法

例题

受欢迎的牛G

The Cow Prom S

【模板】缩点

原理

定义

时间戳 dfn[x]：节点 \(x\) 第一次被访问的顺序

追溯值 low[x]：节点 \(x\) 能访问到时间戳最小的值

对能够访问的定义：（以下两个条件满足其一即可）

• 以 \(x\) 为根的搜索树的所有节点（实际上以 \(x\) 为根的搜索树的子节点的时间戳一定大于 \(x\) 的时间戳）

• 通过一条非搜索树（返祖边与横叉边）上的边，能够到达搜索树的所有节点

搜索过程

1. 开始搜索节点 \(x\) 时，对 \(x\) 盖上时间戳并入栈

2. 枚举 \(x\) 的相邻顶点 \(y\) ，分三种情况：

   若 \(y\) 没有被访问过，那么对 \(y\) 深度搜索。在重新访问到 \(x\) 的时候，用 low[y] 更新 low[x] 。这是因为 \(x\) 是 \(y\) 的父节点，只要 \(y\) 能够访问到，那么x也一定能访问到。

   若y已经访问且在栈中：说明 \(y\) 是祖先节点或者左子树节点，那么用 dfn[n] 更新 low[x] 。

   若y已访问且不在栈中，说明 \(y\) 已经搜索完毕，因为其连通分量已被处理，所以不用对其做操作。

3. 对节点 \(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;
}