拓扑排序好题。
首先需要一个比较显然但从来没用过的性质，任何时刻，队列中的点都不可能相互之间有你到我，或者我到你的关系。
所以当枚举到一个点，出现队列中除了他还有两个及以上的数，那么这个点就一定不可能被统计到答案中。
考虑没有点的情况，也就是说剩下的点都只能由他拓展出来，所以他可以到达剩下的所有点。
考虑有一个点的情况，记为 \(b\)，当 \(b\) 能去的点中有度数为 \(1\) 的点，那么也就是说那个度数为 \(1\) 的点，只能由 \(b\) 拓展得到，那么还存在 \(u\) 到不了的点，所以 \(u\) 也无法被统计答案。
最后统计一下能到的点大于等于 \(n-1\) 且满足合法的点的答案即可。
时间复杂度 \(O(n)\)
点击查看代码
#include<bits/stdc++.h>
typedef long long LL;
using namespace std;
const int MAXN=3e5+10;
int n,m;
struct daduoli {
int f,t;
}a[MAXN];
int f[MAXN],in[MAXN];
vector<int> e[MAXN];
void add(int f,int t) {
e[f].push_back(t);
}
bool vis[MAXN];
void zx(int opt) {
int rest=n;
queue<int> q;
for(int i=1;i<=n;++i) {
if(!in[i]) {
q.push(i);
--rest;
}
}
while(!q.empty()) {
int u=q.front();
q.pop();
if(q.size()>=2) vis[u]=1;
else if(!q.empty()) {
int v=q.front(),tt=0;
for(auto t:e[v]) {
if(in[t]==1) vis[u]=1;
}
f[u]+=rest-tt;
}
else f[u]+=rest;
for(auto t:e[u]) {
--in[t];
if(!in[t]) {
--rest;
q.push(t);
}
}
}
}
int main () {
scanf("%d%d",&n,&m);
for(int i=1;i<=m;++i) {
scanf("%d%d",&a[i].f,&a[i].t);
}
for(int i=1;i<=m;++i) {
++in[a[i].t];
add(a[i].f,a[i].t);
}
zx(0);
memset(in,0,sizeof(in));
for(int i=1;i<=n;++i) e[i].clear();
for(int i=1;i<=m;++i) {
++in[a[i].f];
add(a[i].t,a[i].f);
}
zx(1);
int ans=0;
for(int i=1;i<=n;++i) {
if(!vis[i]&&f[i]>=n-2) {
++ans;
}
}
printf("%d\n",ans);
return 0;
}