[Luogu 2341] HAOI2006 受欢迎的牛
智能推的水题,一看是省选题就给做了,做一半才发现 Tarjan 算法忘干净了。
Tarjan 求出SCC,算出每一个 SCC 包含原图的点数(size)以及新图上的出度(out)
并不用建图,Tarjan 时记一下 SCC 编号和 size,缩点时记录 out 就好了。
若存在唯一出度为 \(0\) 的 SCC,则这个 SCC 中所有的牛都是明星,即明星数量为这个 SCC 的 out。
否则答案为 \(0\)。
#include#include #include using std::min;using std::stack;const int MAXN=10010,MAXM=50010;bool exist[MAXN];int n,m,cnt,num,sum,head[MAXN],DFN[MAXN],low[MAXN],SCC[MAXN],size[MAXN],out[MAXN];stack st;struct edge{ int nxt,to; edge(int nxt=0,int to=0):nxt(nxt),to(to){}}e[MAXM];void AddEdge(int u,int v){ e[++cnt]=edge(head[u],v),head[u]=cnt;}void Tarjan(int u){ st.push(u),exist[u]=1,DFN[u]=low[u]=++num; for(int i=head[u],v;i;i=e[i].nxt) if(!DFN[v=e[i].to]) Tarjan(v),low[u]=min(low[u],low[v]); else if(exist[v]) low[u]=min(low[u],DFN[v]); if(DFN[u]==low[u]) { ++sum; for(int t;u!=t;) exist[t=st.top()]=0,st.pop(),++size[SCC[t]=sum]; }}void Shrink(void){ for(int u=1;u<=n;++u) for(int i=head[u],v;i;i=e[i].nxt) if(SCC[u]^SCC[v=e[i].to]) ++out[SCC[u]];}int Ans(void){ int ans=0; for(int i=1;i<=sum;++i) if(!out[i]) if(ans) return 0; else ans=size[i]; return ans;}int main(int argc,char *argv[]){ scanf("%d %d",&n,&m); for(int i=1,u,v;i<=m;++i) { scanf("%d %d",&u,&v); AddEdge(u,v); } for(int i=1;i<=n;++i) if(!DFN[i]) Tarjan(i); Shrink(); printf("%d\n",Ans()); return 0;}
谢谢阅读。