题意
一张 (n) 点 (m) 边的 (DAG) ，问有多少个点满足最多存在一个点不能够到它或者它不能到。
(n,mleq 3 imes 10^5)
分析
-
考虑拓扑排序，如果 (A) 能够到 (B) ，那么 (A,B) 一定不能同时存在于队列中。
-
所以如果队列中同时存在的点超过了2个，队列中的点都是不合法的。
-
如果队列中只有一个点，那么剩下的没进队的点他都可以到达；如果队列中有两个点 (a,b)，且 (b) 能够到达一个入度为1的点 (c)，此时 (a) 一定不能够到 (c) ,否则 (a) 可以到剩下所有的点.
-
然而一对点不能互相到达不一定体现在同时存在于队列中，因为可能 (a) 已经出队后 (b) 才进队。但是 (a) 一定不会出现在 (b) 能够到达(被到达)的点集中(反向建边再跑一遍求被到达)，所以判断每个点能够到达(被到达)的点集大小是否 (geq n-2) 即可。
-
总时间复杂度为 (O(n)) 。
代码
#include<bits/stdc++.h>
using namespace std;
#define go(u) for(int i=head[u],v=e[i].to;i;i=e[i].lst,v=e[i].to)
#define rep(i,a,b) for(int i=a;i<=b;++i)
#define pb push_back
typedef long long LL;
inline int gi(){
int x=0,f=1;char ch=getchar();
while(!isdigit(ch)) {if(ch=='-') f=-1;ch=getchar();}
while(isdigit(ch)){x=(x<<3)+(x<<1)+ch-48;ch=getchar();}
return x*f;
}
template<typename T>inline bool Max(T &a,T b){return a<b?a=b,1:0;}
template<typename T>inline bool Min(T &a,T b){return b<a?a=b,1:0;}
const int N=3e5 + 7;
int edc,n,m,sel;
int head[N],mark[N],u[N],v[N],ind[N],f[N],q[N],hd,tl;
struct edge{
int lst,to;
edge(){}edge(int lst,int to):lst(lst),to(to){}
}e[N*2];
void Add(int a,int b){
e[++edc]=edge(head[a],b),head[a]=edc;
++ind[b];
}
void solve(int x,int y,int w){
bool fg=0;
go(y) if(ind[v]==1){fg=1;break;}
if(fg) mark[x]=1;
else f[x]+=w;
}
void topo(){
hd=1,tl=0;
rep(i,1,n) if(!ind[i]) q[++tl]=i;
for(;hd<=tl;++hd){
int u=q[hd];
if(hd==tl) f[u]+=n-tl;
if(tl-hd==1) solve(q[tl-1],q[tl],n-tl);
go(u)if(--ind[v]==0) q[++tl]=v;
}
}
int main(){
n=gi(),m=gi();
for(int i=1;i<=m;++i){
u[i]=gi(),v[i]=gi();
Add(u[i],v[i]);
}
topo();
memset(ind,0,sizeof ind);
memset(head,0,sizeof head);edc=0;
rep(i,1,m) Add(v[i],u[i]);
topo();
int ans=0;
rep(i,1,n) if(!mark[i]&&f[i]+1>=n-1) ++ans;
printf("%d
",ans);
return 0;
}