题目大意:给你一张有向图,在一个点上的信息能沿着有向边扩散到另一个点,然后可以继续扩散。问至少把信息给多少个点,才能使所有点都收到信息。
解题思路:首先求强连通分量缩点,一个强连通分量里的一定能从任意一个点传播到另一个点。
用Tarjan缩点即可。
然后只要找新图拓扑序中入度为0的点即可,因为入度不为0的点一定能从另一个点得到信息,而入度为0的点无法从别的点上得到信息。
由于我们只需要找入度为0的点,而不关心每个点的入度实际是多少,所以只需要用原图的边即可,只要连接的两个点属于不同的强连通分量,就给终点所属的强连通分量入度+1。最后统计答案即可。
C++ Code:
#include<cstdio> #include<cctype> #include<cstring> #define N 100005 int n,m,head[N],dfn[N],low[N],sta[N],stk,idx,ltfl,ys[N],deg[N]; bool vis[N]; struct edge{ int from,to,nxt; }e[1000005]; inline int readint(){ char c=getchar(); for(;!isdigit(c);c=getchar()); int d=0; for(;isdigit(c);c=getchar()) d=(d<<3)+(d<<1)+(c^'0'); return d; } void tarjan(int now){ vis[sta[++stk]=now]=true; dfn[now]=low[now]=++idx; for(int i=head[now];i;i=e[i].nxt) if(!dfn[e[i].to]){ tarjan(e[i].to); if(low[now]>low[e[i].to])low[now]=low[e[i].to]; }else if(vis[e[i].to]&&low[now]>dfn[e[i].to]) low[now]=dfn[e[i].to]; if(low[now]==dfn[now]){ ++ltfl; int k; do{ k=sta[stk--]; vis[k]=false; ys[k]=ltfl; }while(k!=now); } } int main(){ stk=ltfl=0; n=readint(),m=readint(); for(int i=1;i<=m;++i){ int u=readint(),v=readint(); e[i]=(edge){u,v,head[u]}; head[u]=i; } memset(dfn,0,sizeof dfn); memset(low,0,sizeof low); for(int i=1;i<=n;++i) if(!dfn[i]){ memset(vis,0,sizeof vis); idx=0; tarjan(i); } memset(deg,0,sizeof deg); for(int i=1;i<=m;++i) if(ys[e[i].from]!=ys[e[i].to]) ++deg[ys[e[i].to]]; int ans=0; for(int i=1;i<=ltfl;++i) if(!deg[i])++ans; printf("%d ",ans); return 0; }