首页 > 代码库 > 洛谷 P2341 BZOJ 1051 [HAOI2006]受欢迎的牛
洛谷 P2341 BZOJ 1051 [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
解题思路
tarjan找到强连通分量，然后缩点，统计缩了之后每个强连通分量的出度，如果只有一个出度为零的强连通分量，答案就是这个强连通分量里点的个数；如果出度为零的强连通分量不止一个，那么答案就为0。
记得Neil做这题的时候曾经疑惑过——如果缩点后得到的图还是成环咋办？那么所有强连通分量出度都不为零了，答案应该为0，但事实上应该所有奶牛都受欢迎了……原来这个算法正确性是这么保证的——tarjan算法有一个性质：求出的强连通分量一定是极大强连通分量，所以缩出来的点肯定不会成环。
源代码
#include<cstdio>#include<algorithm>int n,m;struct edge{ int u,v;}b[100010];struct Edge{ int nxt,to;}e[100010];int head[100010]={0},cnt=1;void add(int u,int v){ e[cnt]={head[u],v}; head[u]=cnt++;}int id[100010]={0},index=0;int num[100010]={0};int dfn[100010]={0},low[100010]={0},dfs_time=0;int stack[100010]={0},top=0;bool instack[100010]={0};void tarjan(int u){ low[u]=dfn[u]=++dfs_time; stack[top++]=u; instack[u]=1; for(int i=head[u];i;i=e[i].nxt) { int v=e[i].to; if(!dfn[v]) tarjan(v),low[u]=std::min(low[v],low[u]); else if(instack[v]) low[u]=std::min(low[v],low[u]); } if(dfn[u]==low[u]) { index++; int v; do{ v=stack[--top]; stack[top]=0; id[v]=index,instack[v]=0; num[index]++; }while(v!=u); }}int out[100010]={0};int main(){ //freopen("cow.in","r",stdin); //freopen("cow.out","w",stdout); scanf("%d%d",&n,&m); for(int i=1,u,v;i<=m;i++) { scanf("%d%d",&u,&v); add(u,v); b[i]={u,v}; } for(int i=1;i<=n;i++) if(!dfn[i]) tarjan(i); for(int i=1;i<=m;i++) if(id[b[i].u]!=id[b[i].v]) out[id[b[i].u]]++; int ans=0; for(int i=1;i<=index;i++) if(!out[i]) { if(ans) { printf("0\n"); return 0; } else ans=num[i]; } printf("%d\n",ans); return 0;}
洛谷 P2341 BZOJ 1051 [HAOI2006]受欢迎的牛
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。