/*
考虑图
4 5
1 2
2 3
3 1
3 4
4 2
栈里点状态变化
node	dfn	low
1		1	1
👇
node	dfn	low
2		2	2
1		1	1
👇
node	dfn	low
3		3	3
2		2	2
1		1	1
👇tarjan(3)过程中先遍历边3->1
node	dfn	low
3		3	1
2		2	2
1		1	1
👇tarjan(3)过程中先遍历边3->1再遍历3->4
node	dfn	low
4		4	2
3		3	1
2		2	2
1		1	1
👇tarjan(2) 中在遍历2->3过程中完成tarjan(3)后 因为是从if(!dfs[y])分支进的tarjan(3)，所以执行min(low[x], low[y])保证必须用更新过的low
	node	dfn	low
	4		4	2
	3		3	1
	2		2	1
	1		1	1


考虑图
-----
（1单独一个强连通分量）
4 4
2 3
3 4
4 2
3 1
-----
5 6
1 2
2 3
3 4
4 1
4 5
5 3
-----
4 4
2 3
3 4
4 2
3 1
*/
#include<bits/stdc++.h>
using namespace std;
const int maxn=5E4+10, maxm=5E4+10;
int a, b, n, m, scc_cnt=1, low[maxn], dfs[maxn], ans, dfn=1;
int st[maxn], st_size=0, node_scc_id[maxn];
vector<int> g[maxn], scc[maxn];
void tarjan(int x){
	dfs[x]=low[x]=dfn++;//标记dfs访问顺序：dfs[]；   最小能根据边搜到的dfn：low[]
	st[st_size++]=x;//st入栈，便于综合处理scc
	for(int j=0; j<g[x].size(); j++){
		int y=g[x][j];
		if(!dfs[y]){
			tarjan(y);//大框架是dfs递归
			low[x]=min(low[x], low[y]);//存在x->y边，故y能到的最小索引x必然能到
		}else if(!node_scc_id[y]){//如果dfs访问过y点了，关注在栈中（没完成缩点）的点
			low[x]=min(low[x], dfs[y]);//写成low[y]也能A。y在栈中即y在当前处理的SCC中，此时保证dfs[y]==low[y]
		}
	}
	if(low[x]==dfs[x]){//强连通分量找到环的一个切入口
		int y;
		do{
			y=st[--st_size];//栈顶到low[x]==dfs[x]这个点都属于同一个SCC极大子图
			scc[scc_cnt].push_back(y);//第scc_cnt个scc包含y点
			node_scc_id[y]=scc_cnt;//本题中node_scc_id主要功能是标记已经出栈，为实现bool效果scc_cnt要初始化为1而非0，网上很多示例代码专门用instack数组标记。
			//其实还实现了记录点y属于第scc_cnt个scc，接下来缩点做准备P3387. 【模板】缩点 
		}while(x!=y);
		scc_cnt++;
	}
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin>>n>>m;
	for(int i=1; i<=m; i++){
		cin>>a>>b;
		g[a].push_back(b);
	}
	for(int i=1; i<=n; i++){
		if(!dfs[i])	tarjan(i);//dfs序标记过就不用访问了
	}
	for(int i=1; i<scc_cnt; i++){
		// for(int j=0; j<scc[i].size(); j++){
		// 	cout<<scc[i][j]<<" ";
		// }
		// cout<<"\n打印一组SCC\n";
		if(scc[i].size()>1){
			ans++;
		}
	}
	cout<<ans;
	return 0;
}

老师的代码把找 dfn 的过程和 tarjan 合并了，有点看不懂，我贴个自己的代码。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e4 + 5,M = 5e4 + 5;
int n,m,tot,dfn[N],low[N],cnt;
bool f[N],is[N];
// f[i] 表示 i 走过没有；is[i] 表示 i 是否在栈内
vector<int> a[N],root;
void dfs(int u){
	dfn[u] = ++tot,low[u] = dfn[u];
	for (int v : a[u]){
		if (!dfn[v])	dfs(v);
	}
}
stack<int> s;
void tarjan(int u){
	s.push(u);
	f[u] = 1;
	is[u] = 1;
	for (int v : a[u]){
		if (!f[v])	tarjan(v);
		if (is[v])	low[u] = min(low[u],low[v]);
	}
	if (dfn[u] == low[u]){
		int sz = 1;
		while (s.top() != u){
			sz++;
			is[s.top()] = 0;
			s.pop();
		}
		s.pop();
		is[u] = 0;
		if (sz > 1)	cnt++;
	}
}
int main(int argc, char **argv){
	cin >> n >> m;
	for (int i = 1;i <= m;i++){
		int u,v;
		cin >> u >> v;
		a[u].push_back(v);
	}
	for (int i = 1;i <= n;i++){
		if (!dfn[i])	dfs(i),root.push_back(i);
	}
	// for (int i = 1;i <= n;i++)	printf("%d:%d ",i,dfn[i]);
	for (int i : root)	tarjan(i);
	// cout << '\n';
	// for (int i = 1;i <= n;i++)	printf("%d:%d ",i,low[i]);
	cout << cnt;
	return 0;
}