lgP2341[HAOI2006]受欢迎的牛 发表于 2018-04-03 | 分类于 算法 , 图论 , tarjan | 阅读数 次 链接:lgP2341[HAOI2006]受欢迎的牛 题解 爱慕可以传递,很自然想到缩点,所以只需要找到可以被所有缩点遍历到的那个缩点,自然想到出度为零的缩点就是我们要求的 但是如果有两个这样的缩点,自然无解,然后很迷人的操作WA 3发 123456789101112131415161718192021222324252627282930313233343536373839404142434445#include<iostream>#include<cstdio>#include<cstdlib>#include<cmath>#include<cstring>#include<algorithm>#define rep(i,x,y) for(register int i=x;i<=y;++i)#define repd(i,x,y) for(register int i=x;i>=y;--i)#define ll long longusing namespace std;const int N=1e6;struct node{ int v,nxt; inline void init(int a,int b){v=a;nxt=b;}}e[N];int head[N],cnt,n,m,dfn[N],low[N],tot,ans[N],idx,stck[N],in[N],lg[N],du[N],tp;inline void adde(int x,int y){e[cnt].init(y,head[x]);head[x]=cnt++;}void tarjan(int u){ in[u]=1; stck[++idx]=u; dfn[u]=low[u]=++tot; for(int i=head[u],v;i!=-1;i=e[i].nxt){ if(!dfn[v=e[i].v]){ tarjan(v); low[u]=min(low[u],low[v]); } else if(in[v])low[u]=min(low[u],dfn[v]); } if(dfn[u]==low[u]){ int x; cnt++; do{in[idx]=0;lg[stck[idx--]]=cnt;ans[cnt]++;}while(stck[idx+1]!=u); }}int main(){ memset(head,-1,sizeof(head)); scanf("%d%d",&n,&m); rep(i,1,m){int x,y;scanf("%d%d",&x,&y);adde(x,y);}cnt=0; rep(i,1,n)if(!dfn[i])tarjan(i); rep(i,1,n)for(int j=head[i];j!=-1;j=e[j].nxt)if(lg[e[j].v]!=lg[i])du[lg[i]]++; rep(i,1,cnt)if(!du[i]){if(tp){puts("0");return 0;} tp=i;} printf("%d",ans[tp]); return 0;}