又是一道Tarjan水题，这次经过仔细的思考，没有打错邻接表（图论已入门qwq）。

还是先来说说思路吧，由题意知，就是给一张n个点，m条边的有向图，让你求出有多少个点可以由所有的点达到。

有如下定理：若在有向图中有且仅有一个点出度为零，那么所有点都可达到它（传说中的反证法可以证明它（真的吗，我没证出来，逃））。

但是这是一个点啊，怎么搞出所有点呢？注意先前的论述中，有“所有点可达”这一字样，那么什么算法中还有这些字呢（模拟暴搜除外）？当然是强连通们啊！！！所以本题的思路就很明确了：Tarjan求强连通（别的也行），再缩点，在缩过点的邻接表中统计出度为零的点。

具体操作呢？看代码呗qwq。

#include
    
     using namespace std;#define maxn 50005struct Edge{	int u,v;}e[maxn<<1],e2[maxn<<1];int first[maxn],next[maxn<<1],first2[maxn],next2[maxn<<1],cnt=0,cnt2=0;int out[10005];void AddEdge(int u,int v){	e[++cnt].u=u;e[cnt].v=v;	next[cnt]=first[u];first[u]=cnt;}void AddEdge2(int u,int v){	e2[++cnt2].u=u;e2[cnt2].v=v;	next2[cnt2]=first2[u];first2[u]=cnt2;}int pre[maxn],lowlink[maxn],sccno[maxn],dfs_clock,scc_cnt;stack
     
       S;void Tarjan(int u){	pre[u]=lowlink[u]=++dfs_clock;	S.push(u);	for(int i=first[u];i;i=next[i]){		int v=e[i].v;		if(!pre[v]){			Tarjan(v);			lowlink[u]=min(lowlink[u],lowlink[v]);		}		else if(!sccno[v]){			lowlink[u]=min(lowlink[u],pre[v]);		}	}	if(lowlink[u]==pre[u]){		scc_cnt++;		for(;;){			int x=S.top(); S.pop();			sccno[x]=scc_cnt;			if(x==u) break;		}	}}void find_scc(int n){	memset(pre,0,sizeof(pre));	memset(sccno,0,sizeof(sccno));	for(int i=1;i<=n;i++)		if(!pre[i]) Tarjan(i);}int main(){	int n,m;	scanf("%d%d",&n,&m);	for(int i=1;i<=m;i++){		int u,v;		scanf("%d%d",&u,&v);		AddEdge(u,v);	}	find_scc(n);	for(int i=1;i<=n;i++)		for(int j=first[i];j;j=next[j])			if(sccno[i]!=sccno[e[j].v])				AddEdge2(sccno[i],sccno[e[j].v]);	for(int i=1;i<=scc_cnt;i++)		for(int j=first2[i];j;j=next[j])			out[i]++;	int ans=0,star=0,num=0;	for(int i=1;i<=scc_cnt;i++)		if(!out[i]){			num++;			star=i;		}	if(num==1){		for(int i=1;i<=n;i++)			if(sccno[i]==star) ans++;		printf("%d\n",ans);	}	else printf("0\n");	return 0;}
     
    

如果像我一样的萌（ju）新（ruo）有不太懂缩点的，我会在以后的文章中作为OI学习总结再次提到。