N<=1000
邪恶的想法就产生了,暴力枚举每个点,$O(n^2)$也能过
正着做一遍bfs 倒着做一遍bfs 把能到达的点都标记上,最后统计一下就行了
#include <bits/stdc++.h>
using namespace std;
const int N = 1010, M = 30010;
int h1[N],h2[N], e[M], ne[M], idx;
bool st[N];
bool can1[N],can2[N];
int n,m;
void add(int a, int b, int h[]) // 添加一条边a->b
{
e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}
void bfs(int u,int h[],bool s[]){
queue<int> q;
q.push(u);
s[u]=true;
while(q.size()){
int t=q.front();q.pop();
for(int i=h[t];~i;i=ne[i]){
int j=e[i];
if(s[j]) continue;
s[j]=true;
q.push(j);
}
}
}
int main()
{
scanf("%d%d", &n, &m);
memset(h1, -1, sizeof h1);
memset(h2, -1, sizeof h2);
while (m -- ){
int a,b;
scanf("%d%d", &a, &b);
add(a, b, h1);
add(b, a, h2);
}
int ans=0;
for(int i=1;i<=n;i++){
memset(can1,0,sizeof can1);
memset(can2,0,sizeof can2);
bfs(i,h1,can1);
bfs(i,h2,can2);
int cnt=0;
for(int j=1;j<=n;j++){
if(can1[j]||can2[j]) cnt++;
}
if(cnt==n) ans++;
}
printf("%d",ans);
return 0;
}