思路

首先我们可以发现，在任意一个节点数量大于 \(1\) 的强连通分量中的点都满足条件。

所以，我们可以对这张图跑一边 TarJan。

但是这样是错的，因为我们还需要考虑节点数量为 \(1\) 的强连通分量。

如果这种连通分量能够到达任意一个节点数量大于 \(1\) 的强连通分量，那么，这个连通分量也满足条件。

所以，我们在缩完点后，反向建边，对于所有节点数量大于 \(1\) 的强连通分量为起点跑一边 DFS 即可。

因为每一个点最多会被遍历一次，所以时间复杂度为 \(\Theta(n + m)\)。

code

#include <bits/stdc++.h>
#define re register

using namespace std;

const int N = 2e5 + 10;
int n,m,ans;
int tim,num,dfn[N],low[N],sz[N],id[N];
bool vis[N];
stack<int> st;

struct edge{
	int idx,h[N],ne[N],e[N];
	
	inline void init(){
		memset(h,-1,sizeof(h));
	}
	
	inline void add(int a,int b){
		ne[idx] = h[a];
		e[idx] = b;
		h[a] = idx++;
	}
}g[2];

inline int read(){
	int r = 0,w = 1;
	char c = getchar();
	while (c < '0' || c > '9'){
		if (c == '-') w = -1;
		c = getchar();
	}
	while (c >= '0' && c <= '9'){
		r = (r << 1) + (r << 3) + (c ^ 48);
		c = getchar();
	}
	return r * w;
}

inline void tarjan(int u){
	dfn[u] = low[u] = ++tim;
	vis[u] = true;
	st.push(u);
	for (re int i = g[0].h[u];~i;i = g[0].ne[i]){
		int j = g[0].e[i];
		if (!dfn[j]){
			tarjan(j);
			low[u] = min(low[u],low[j]);
		}
		else if (vis[j]) low[u] = min(low[u],low[j]);
	}
	if (dfn[u] == low[u]){
		int x;
		num++;
		do{
			x = st.top();
			st.pop();
			sz[num]++;
			id[x] = num;
			vis[x] = false;
		}while (x != u);
	}
}

inline void dfs(int u){
	vis[u] = true;
	for (re int i = g[1].h[u];~i;i = g[1].ne[i]){
		int j = g[1].e[i];
		if (vis[j]) continue;
		dfs(j);
	}
}

int main(){
	g[0].init();
	g[1].init();
	n = read();
	m = read();
	for (re int i = 1;i <= m;i++){
		int a,b;
		a = read();
		b = read();
		g[0].add(a,b);
	}
	for (re int i = 1;i <= n;i++){
		if (!dfn[i]) tarjan(i);
	}
	for (re int u = 1;u <= n;u++){
		for (re int i = g[0].h[u];~i;i = g[0].ne[i]){
			int j = g[0].e[i];
			if (id[u] != id[j]) g[1].add(id[j],id[u]);
		}
	}
	memset(vis,false,sizeof(vis));
	for (re int u = 1;u <= num;u++){
		if (sz[u] > 1) dfs(u);
	}
	for (re int u = 1;u <= num;u++){
		if (vis[u]) ans += sz[u];
	}
	printf("%d",ans);
	return 0;
}