这个题其实就是tarjan缩点的板子题对吧....至少我是这么想的
首先这是个有向图,对于一个有向图,我们肯定要考虑环的存在与否,恰好这个题又是让我们找出最少的点,使得这几个点能够走遍全图
那么,显然,对于每一个强连通分量,我们看做一个点即可(因为强连通分量中每两个点之间一定能从一个点到另一个点,即从一个点出发一定能够走遍整个强连通分量)
缩完点之后,我们得到一个DAG,显然,对于每一个入度为零的点,我们都需要发布消息,其余入度不为零的点都可以通过这些入度为零的点走到
于是,这题就A了
#include #include #include using namespace std;const int N=1e5+5;const int M=5e5+5;struct edge{ int to,next;}e[M];int n,m,dfn[N],low[N],cnt,head[N];int idx[N],s[N],top,tot,sum;bool ins[N];int ind[N],ans;inline void build(int u,int v){ e[++tot].next=head[u]; head[u]=tot; e[tot].to=v; return ;}inline void tarjan(int cur){ s[++top]=cur;ins[cur]=true; dfn[cur]=low[cur]=++cnt; for(int i=head[cur];i;i=e[i].next){ int k=e[i].to; if(!dfn[k]){ tarjan(k); low[cur]=min(low[cur],low[k]); }else if(ins[k]) low[cur]=min(low[cur],dfn[k]); } if(low[cur]==dfn[cur]){ ++sum; while(s[top+1]!=cur){ idx[s[top]]=sum; ins[s[top--]]=false; } } return ;}int main(){ scanf("%d%d",&n,&m); for(int i=1;i<=m;++i){ register int u,v; scanf("%d%d",&u,&v); build(u,v); } for(int i=1;i<=n;++i) if(!dfn[i]) tarjan(i); for(int i=1;i<=n;++i) for(int j=head[i];j;j=e[j].next){ int k=e[j].to; if(idx[i]!=idx[k]) ++ind[idx[k]]; } for(int i=1;i<=sum;++i) if(!ind[i]) ++ans; printf("%d\n",ans); return 0;}