[HAOI2006]受欢迎的牛
【题目描述】
每一头牛的愿望就是变成一头最受欢迎的牛。现在有N头牛，给你M对整数（A，B），表示牛 A 认为牛
B受欢迎。这种关系是具有传递性的，如果A认为B受欢迎，B认为C受欢迎，那么牛A也认为牛C受欢迎。你的任务是求出有多少头牛被所有的牛认为是受欢迎的。
【输入格式】
第1行两个整数N，M；
接下来M行，每行两个数A，B，意思是A认为B是受欢迎的（给出的信息有可能重复，即有可能出现多个A，B）
【输出格式】
一个数，即有多少头牛被所有的牛认为是受欢迎的。
【样例输入】
3 3 1 2 2 1 2 3
【样例输出】
1
【数据范围】
10%的数据N<=20,M<=50
30%的数据N<=1000,M<=20000
70%的数据N<=5000,M<=50000
100%的数据N<=10000,M<=50000
1 /* 2 明显tarjan缩点 3 输入可能重复 那就只好从出度下手 4 跑缩点后的图 5 找没有出度的点 6 若只有一个这样的点 就输出数量 7 否则就为0 8 因为若有两个这样的点 9 那么没有牛是被所有牛所喜爱的 自己想一想吧 10 */ 11 #include <cstdio> 12 #include <ctype.h> 13 14 const int MAXN=10010; 15 const int MAXM=50010; 16 17 int n,m,cnt,top,id; 18 19 int dfn[MAXN],low[MAXN]; 20 21 int stack[MAXN],belong[MAXN],in[MAXN],sum[MAXN]; 22 23 bool vis[MAXN]; 24 25 struct EDG { 26 int to; 27 int next; 28 }; 29 EDG e[MAXM<<1]; 30 31 int head[MAXN],tot; 32 33 inline void read(int&x) { 34 int f=1;register char c=getchar(); 35 for(x=0;!isdigit(c);c=='-'&&(f=-1),c=getchar()); 36 for(;isdigit(c);x=x*10+c-48,c=getchar()); 37 x=x*f; 38 } 39 40 inline int min(int a,int b) { 41 return a<b?a:b; 42 } 43 44 inline void add(int x,int y) { 45 e[++tot].to=y; 46 e[tot].next=head[x]; 47 head[x]=tot; 48 } 49 50 void tarjan(int u) { 51 dfn[u]=low[u]=++cnt; 52 vis[u]=true; 53 stack[++top]=u; 54 for(register int i=head[u];i;i=e[i].next) { 55 int v=e[i].to; 56 if(!dfn[v]) { 57 tarjan(v); 58 low[u]=min(low[u],low[v]); 59 } 60 else if(vis[v]) low[u]=min(low[u],dfn[v]); 61 } 62 if(dfn[u]==low[u]) { 63 ++id; 64 int t; 65 do { 66 t=stack[top]; 67 --top; 68 belong[t]=id; 69 vis[t]=false; 70 ++sum[id]; 71 }while(u!=t); 72 } 73 return; 74 } 75 76 int hh() { 77 freopen("cow.in","r",stdin); 78 freopen("cow.out","w",stdout); 79 read(n);read(m); 80 for(register int x,y;m--;) { 81 read(x);read(y); 82 add(x,y); 83 } 84 for(register int i=1;i<=n;++i) 85 if(!dfn[i]) tarjan(i); 86 for(register int i=1;i<=n;++i) 87 for(register int j=head[i];j;j=e[j].next) { 88 int v=e[j].to; 89 if(belong[i]!=belong[v]) { 90 in[belong[i]]++; 91 } 92 } 93 int ans=0,tot=0,t=0; 94 for(register int i=1;i<=id;++i) 95 if(!in[i]) ++tot,ans+=sum[i]; 96 printf("%d ",tot==1?ans:t); 97 return 0; 98 } 99 100 int sb=hh(); 101 int main() {;}