受欢迎的牛

题目描述

一些可以当明星的牛,一定会构成一个强连通分量,我们可以先缩点,最后统计一下出度为零的强连通分量大小即可,

若出度为零的强连通分量个数大于1,则输出0

 #include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
#define N 10010
#define M 100010
int n,m,dfn[N],low[N],belong[N],du[N],cnt;
int stack[N],top,size[N],k,head[N],num,tot;
bool instack[N];
struct NODE{
int to,next;
} e[M];
inline int read(){
int x=,f=; char c=getchar();
while(c<''||c>'') { if(c=='-') f=-; c=getchar(); }
while(''<=c&&c<='') { x=(x<<)+(x<<)+c-''; c=getchar(); }
return x*f;
}
inline void add(int x,int y)
{
e[++num].to=y;
e[num].next=head[x];
head[x]=num;
}
void Tarjan(int u){
dfn[u]=low[u]=++cnt;
stack[++top]=u;
instack[u]=;
for(int i=head[u];i;i=e[i].next)
if(!dfn[e[i].to]){
Tarjan(e[i].to);
low[u]=min(low[u],low[e[i].to]);
}
else if(instack[e[i].to])
low[u]=min(low[u],dfn[e[i].to]);
if(low[u]==dfn[u]){
belong[u]=++tot;
size[tot]++;    //记录强连通分量大小
while(stack[top]!=u){
int t=stack[top];
belong[t]=tot;
instack[t]=;
size[tot]++;
top--;
}
top--;
instack[u]=;
}
}
int main()
{
scanf("%d%d",&n,&m);
int x,y;
for(int i=;i<=m;i++){
x=read(); y=read();
add(x,y);
}
for(int i=;i<=n;i++)
if(!dfn[i])
Tarjan(i);
for(int i=;i<=n;i++)
for(int j=head[i];j;j=e[j].next)  //统计出度
if(belong[i]!=belong[e[j].to])
du[belong[i]]++;
int ans=;
for(int i=;i<=tot;i++)
if(!du[i]){
ans=size[i];
k++;
}
if(k==)
printf("%d\n",ans);
else puts("");
return ;
}

最新文章

  1. MEF 根据配置注入Service
  2. 初识 Android
  3. apt-get常用命令
  4. eclipse svn subclipse下载地址
  5. ArrayAdapter的简单使用
  6. 利用JQ实现的,高仿 彩虹岛官网导航栏(学习HTML过程中的小记录)
  7. repeater复杂表格的显示
  8. XML参数转换为Object,并转换为List或DataTable
  9. hadoop集群中的日志文件
  10. 深入浅出Win32多线程设计之MFC的多线程-线程与消息队列(经典)
  11. caffe CuDNN报错问题解决
  12. leetcode【67】-Bulb Switcher
  13. springcloud情操陶冶-springcloud config server(一)
  14. Centos 7 Puppet之foreman介绍安装测试
  15. 最全面的Redis命令行查阅手册(收藏查看)
  16. M - Pots
  17. ABP之应用服务(1)
  18. Codeforces Round #131 (Div. 1) A - Game
  19. SpringMVC之HandlerMethodArgumentResolver和&lt;mvc:argument-resolvers&gt;
  20. 第8章 ZooKeeper操作

热门文章

  1. java多线程之线程组与线程池
  2. Oracle关于All和Any
  3. C++程序设计基础(8)main函数
  4. bzoj 5291: [Bjoi2018]链上二次求和
  5. 亲测,很有效的忽略SSL证书方法
  6. 【Spring Boot】集成Netty Socket.IO通讯框架
  7. c#解析json字符串处理(最清晰易懂的方法)
  8. php自建静态博客步骤
  9. 编程语言的发展历史剧。(参考https://baijiahao.baidu.com/s?id=1588675986991787716&amp;wfr=spider&amp;for=pc)
  10. 【阿里云产品公测】PTS压力测试最低配ECS性能及评测