首页 > 代码库 > 还是要参加NOIP —— 洛谷 P2341 [HAOI2006]受欢迎的牛
还是要参加NOIP —— 洛谷 P2341 [HAOI2006]受欢迎的牛
题目描述
每头奶牛都梦想成为牛棚里的明星。被所有奶牛喜欢的奶牛就是一头明星奶牛。所有奶
牛都是自恋狂，每头奶牛总是喜欢自己的。奶牛之间的“喜欢”是可以传递的——如果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
练习1
Tarjan缩点
屠龙宝刀点击就送
#include <ctype.h>#include <cstdio>#define M 50050#define N 10050void read(int &x){ x=0;bool f=0; char ch=getchar(); while(!isdigit(ch)) { if(ch==‘-‘) f=1; ch=getchar(); } while(isdigit(ch)) { x=x*10+ch-‘0‘; ch=getchar(); } x=f?(~x)+1:x;}struct node{ int pre,next,to;}edge[M];int min(int a,int b) {return a>b?b:a;} int QLT[N],ans,num,out[N],n,m,head[M],cnt,dfn[N],sumcol,col[N],low[N],T,Stack[N<<1],top;bool vis[N],instack[N];void add(int i,int j){ cnt++; edge[cnt].pre=i; edge[cnt].next=head[i]; edge[cnt].to=j; head[i]=cnt;}void tarjan(int x){ low[x]=dfn[x]=++T; Stack[++top]=x; vis[x]=1; instack[x]=1; for(int i=head[x];i;i=edge[i].next) { int v=edge[i].to; if(instack[v]) low[x]=min(low[x],dfn[v]); else if(!vis[v]) { tarjan(v); low[x]=min(low[x],low[v]); } } if(dfn[x]==low[x]) { sumcol++; while(x!=Stack[top]) { QLT[sumcol]++; instack[Stack[top]]=0; col[Stack[top--]]=sumcol; } instack[Stack[top]]=0; col[Stack[top--]]=sumcol; QLT[sumcol]++; }}int main(){ read(n);read(m); for(int x,y,i=1;i<=m;i++) { read(x); read(y); add(x,y); } for(int i=1;i<=n;i++) if(!vis[i]) tarjan(i); for(int i=1;i<=m;i++) { int u=edge[i].pre,v=edge[i].to; if(col[v]!=col[u]) out[col[u]]++; } for(int i=1;i<=sumcol;i++) if(!out[i]) num++,ans=QLT[i]; num!=1?printf("0"):printf("%d\n",ans); return 0;}
还是要参加NOIP —— 洛谷 P2341 [HAOI2006]受欢迎的牛
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。