图论：tarjan 算法求解强连通分量

题目描述

有一个 $n$ 个点，$m$ 条边的有向图，请求出这个图点数大于 $1$ 的强连通分量个数。

输入格式

第一行为两个整数 $n$ 和 $m$。

第二行至 $m+1$ 行，每一行有两个整数 $a$ 和 $b$，表示有一条从 $a$ 到 $b$ 的有向边。

输出格式

仅一行，表示点数大于 $1$ 的强连通分量个数。

5 4
2 4
3 5
1 2
4 1

1

提示

数据规模与约定

对于全部的测试点，保证 $2\le n\le 10^4$，$2\le m\le 5\times 10^4$，$1\le a,b\le n$。

---

基本概念梳理

强连通图

在一个有向图中，任意两个节点之间都能相互到达，那么这个图就是一个强连通图。

强连通分量（Strongly Connected Components, SCC）

强连通图是非常少的，但是在有向图中，如果存在某些节点子集 $A$，任意两个节点可以相互到达，且如果往子集 $A$ 中再加入新的节点，那么子集中任意两个节点之间无法相互到达，那么称这些节点为强连通分量。如下图，共有三个强连通分量，红框中的节点 $1,2,3$ 组成了一个强连通分量，绿框中的节点 $4,5$ 组成了另一个强连通分量，蓝框中的节点 $6$ 是一个强连通分量。

$DFS$ 遍历

之前我们学习 $DFS$ 遍历的时候，有两种常用的遍历方式。

方式 $1$：先访问当前节点，再递归相邻节点。（类似求树的深度）

方式 $2$：先递归相邻节点，再访问当前节点。（类似求子树大小）

$tarjan$ 算法思路

对于 $tarjan$ 算法，我们用的 $dfs$ 遍历 是上面 方式 $2$。

对于每个节点来说，有两个重要属性，我通常定义为 $id$ 和 $tx$，其中 $id$ 表示 首次到达节点的时间戳，$tx$ 表示从当前节点出发，可以遍历到的 $id$ 最小的节点的值，对于上面的图，我们可以从节点 $1$ 出发进行一次【方式 $2$】 的 $dfs$ 遍历，试试 可以得到每个节点的 $id$ 值和 $tx$ 值分别是多少？如下：

节点 $1:id=1,tx=1$。

节点 $2:id=2,tx=1$。

节点 $3:id=3,tx=1$。

节点 $4:id=4,tx=4$。

节点 $5:id=5,tx=4$。

节点 $6:id=6,tx=6$。

通过观察可以发现，同一个强连通分量中的节点，它们的 $tx$ 值是相等的，而且，强连通分量中的起点的 $id$ 一定等于 $tx$。

在整个 $dfs$ 搜索过程中，我们需要借助 栈 来保存遍历到的元素，到达某个节点后，先从这个节点开始搜，搜索结束后，更新当前节点的 $tx$ 值，所有邻接点全部搜索完后，判断当前节点是否是当前这个强连通分量的起点（即 $id$ 是否等于 $tx$），如果是，从栈空间中取出当前强连通分量的所有节点即可。

比如，找第一个强连通分量，栈结构如下：

此时，对于节点 $1$ 来说，在栈中的位置到栈顶，所有元素都是以 节点 $1$ 为起点的强连通分量中的元素。

其他两个强连通分量类似，在此不画，可以通过代码来理解。

代码

#include "bits/stdc++.h"
using namespace std;
const int N = 2e4+7, M = 5e4+7;
struct Edge{int v, ne;
}es[M];
struct Node{int id, tx;
}f[N];
int n, t=1, m, u, v, idx = 1, h[N], ans;
stack<int> stk;
bool vis[N];  // 记录节点是否在栈中，在栈中标记为true，否则为false
// dfs函数，传入节点编号，开始从当前节点进行 先搜索后访问的 dfs
void dfs(int u) {f[u].id = t;  // 首次到达的时间戳f[u].tx = t++;  // 可以回溯到最小的时间戳，初始的时候就是 t，跟id 一样stk.push(u);   // 当前节点进栈vis[u] = true;  // 所有进栈的元素全部标记for(int e = h[u]; e; e = es[e].ne) {  // 链式前向星遍历节点 u 的所有邻接点int v = es[e].v;  // u 的 邻接点 vif(f[v].id == 0) {   // 节点v 还没有访问过dfs(v);  // 先搜索f[u].tx = min(f[u].tx, f[v].tx);  // 再更新可以回溯到的最小时间戳} else if(vis[v]) {  // 节点v访问过，如果在栈中，那就一定是当前强连通分量中的节点f[u].tx = min(f[u].tx, f[v].tx);  // 更新最小时间戳}}if(f[u].id == f[u].tx) {  // 节点u 是当前强连通分量中的起点，也可以成为当前强连通分量的根节点int cnt = 0; // 本次强连通分量的节点个数，计算的是大于1 的强连通分量的个数while(!stk.empty() && stk.top() != u) {  // 栈顶这些元素都是和 u 一个强连通分量的，而且 u 是这个强连通分量的鼻祖vis[stk.top()] = false;  // 出栈更新visstk.pop();  // 出栈cnt++;  // 强连通分量中节点数+1}vis[stk.top()] = false;  // 本次是 u 节点stk.pop();  // u 出栈cnt++;  // 个数+1if(cnt > 1) ans++;  // 统计点数大于 1 的强连通分量的个数}
}
// 链式前向星建图
void add(int u, int v) {es[idx] = {v, h[u]};h[u] = idx++;return;
}
int main() {cin >> n >> m;while(m--) {cin >> u >> v;add(u, v);   // 有向图}for(int u=1; u<=n; u++) {if(f[u].id == 0) dfs(u);  // 当前节点还没有遍历过，开始从当前节点搜}cout << ans << endl;return 0;
}