每头奶牛都梦想成为牛棚里的明星。被所有奶牛喜欢的奶牛就是一头明星奶牛。所有奶
牛都是自恋狂，每头奶牛总是喜欢自己的。奶牛之间的“喜欢”是可以传递的——如果A喜
欢B，B喜欢C，那么A也喜欢C。牛栏里共有N 头奶牛，给定一些奶牛之间的爱慕关系，请你
算出有多少头奶牛可以当明星。
输入格式：
? 第一行：两个用空格分开的整数：N和M
? 第二行到第M + 1行：每行两个用空格分开的整数：A和B，表示A喜欢B
输出格式：
? 第一行：单独一个整数，表示明星奶牛的数量
只有 3 号奶牛可以做明星
【数据范围】
10%的数据N<=20, M<=50
30%的数据N<=1000,M<=20000
70%的数据N<=5000,M<=50000
100%的数据N<=10000,M<=50000
1 #include <cstdio> 2 #include <iostream> 3 #include <cstring> 4 #include <stack> 5 #define N 10050 6 using namespace std; 7 struct edge{ int from,to; }e[N*20]; 8 int head[20*N],dfn[N],low[N],du[N],p[N],tot[N],cnt,num,n,m,k,o; 9 bool bel[N]; 10 stack<int>Q; 11 void insert(int x,int y) { e[++cnt].to=y,e[cnt].from=head[x],head[x]=cnt; } 12 void tarjan(int x) 13 { 14 dfn[x]=low[x]=++dfn[0],Q.push(x),bel[x]=true; 15 for (int i=head[x];i;i=e[i].from) 16 if (!dfn[e[i].to]) tarjan(e[i].to),low[x]=min(low[x],low[e[i].to]); 17 else if (bel[x]) low[x]=min(low[x],dfn[e[i].to]); 18 if (low[x]==dfn[x]) 19 { 20 ++num; 21 do 22 { 23 k=Q.top(),Q.pop(),bel[k]=false,p[k]=num,tot[num]++; 24 } 25 while (x!=k); 26 } 27 } 28 int main() 29 { 30 scanf("%d%d",&n,&m); 31 for (int i=1,x,y;i<=m;i++) scanf("%d%d",&x,&y),insert(x,y); 32 for (int i=1;i<=n;i++) if (!dfn[i]) tarjan(i); 33 for (int i=1;i<=n;i++) for (int j=head[i];j;j=e[j].from) if (p[i]!=p[e[j].to]) du[p[i]]++; 34 for (int i=1;i<=num;i++) 35 if (!du[i]) 36 { 37 if (o) {printf("0"); return 0;} 38 o=i; 39 } 40 printf("%d",tot[o]); 41 }
原文：https://www.cnblogs.com/Comfortable/p/10328208.html