题目描述
每头奶牛都梦想成为牛棚里的明星。被所有奶牛喜欢的奶牛就是一头明星奶牛。所有奶
牛都是自恋狂，每头奶牛总是喜欢自己的。奶牛之间的“喜欢”是可以传递的——如果A喜
欢B，B喜欢C，那么A也喜欢C。牛栏里共有N 头奶牛，给定一些奶牛之间的爱慕关系，请你
算出有多少头奶牛可以当明星。
输入输出格式
输入格式：
第一行：两个用空格分开的整数：N和M
第二行到第M + 1行：每行两个用空格分开的整数：A和B，表示A喜欢B
输出格式：
第一行：单独一个整数，表示明星奶牛的数量
输入输出样例
输入样例#1：
3 31 22 12 3
输出样例#1：
1
说明
只有 3 号奶牛可以做明星
【数据范围】
10%的数据N<=20, M<=50
30%的数据N<=1000,M<=20000
70%的数据N<=5000,M<=50000
100%的数据N<=10000,M<=50000
最近经常水这些蓝题 雾】
提供一个思路就完事了：Tarjan的思路
如果这个分量中的任意一个点被仰慕，那么说明这个分量中的所有的牛都会被仰慕，那么我们就把这个图全部缩成强连通分量，这个图就变成有向无环图。
这时我们会发现，被所有牛仰慕的牛出度一定是为0的，因为是有向无环图，如果被所有牛仰慕，自己又仰慕别人，那么就会产生一个环。
因为我们只关注一个分量的出度是否为0，所以不用判断两个分量间的边是否重复统计
其次，如果这个图存在一个以上出度为0的强连通分量，这个图就会变成非连通图，就不存在被所有牛仰慕的牛，直接输出0就OK啦。
放上代码。
#include#include #include #include #include #include using namespace std;const int MA=1e4+5;int n,m,sum,ans;int head[MA],ecnt;int low[MA],dfn[MA],ti;int col[MA],cnt[MA],du[MA];bool vis[MA];struct ss{ int self,to,nxt;}t[MA*10];stack s; inline void add(int a,int b) { t[++ecnt].self=a; t[ecnt].nxt=head[a]; t[ecnt].to=b; head[a]=ecnt; return;}inline int read() { int x=0;char ch=getchar(); while(ch<'0'||ch>'9')ch=getchar(); while(ch>='0'&&ch<='9')x=(x<<3)+(x<<1)+ch-'0',ch=getchar(); return x;}void Tar(int x) { dfn[x]=low[x]=++ti; vis[x]=1; s.push(x); for(int i=head[x];i;i=t[i].nxt) { int y=t[i].to; if(!dfn[y]) { Tar(y); low[x]=min(low[x],low[y]); } else if(vis[y]) low[x]=min(low[x],dfn[y]); } int sl; if(dfn[x]==low[x]) { ++ecnt; do{ sl=s.top(); s.pop(); vis[sl]=0; col[sl]=ecnt; cnt[ecnt]++; }while(sl!=x); }}int main(){ n=read(); m=read(); for(int i=1;i<=m;i++) { int a=read(); int b=read(); add(a,b); } ecnt=0; for(int i=1;i<=n;i++) if(!dfn[i]) Tar(i); for(int k=1;k<=n;k++) for(int i=head[k];i;i=t[i].nxt) { int u=t[i].to; if(col[k]!=col[u]) { du[col[k]]++; } } int nw=0; for(int i=1;i<=ecnt;i++) if(!du[i]) { if(nw) { printf("0\n"); return 0; } nw=i; } printf("%d\n",cnt[nw]); return 0;}
完成！
谢谢