bzoj1051 [HAOI2006]受欢迎的牛 tarjan&&缩点
2024-08-31 14:22:02
题目描述
每头奶牛都梦想成为牛棚里的明星。被所有奶牛喜欢的奶牛就是一头明星奶牛。所有奶
牛都是自恋狂,每头奶牛总是喜欢自己的。奶牛之间的“喜欢”是可以传递的——如果A喜
欢B,B喜欢C,那么A也喜欢C。牛栏里共有N 头奶牛,给定一些奶牛之间的爱慕关系,请你
算出有多少头奶牛可以当明星。
输入格式:
第一行:两个用空格分开的整数:N和M
第二行到第M + 1行:每行两个用空格分开的整数:A和B,表示A喜欢B
输出格式:
第一行:单独一个整数,表示明星奶牛的数量
tarjan缩点以后重新建图,如果只有一个点没有出边,那么输出这个强联通分量的大小,否则就没有明星牛。
注意 tarjan缩点时记录每条边连着两点的数组应该开的和变数一样大,我开小就wa了一个点。。。
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
int n,m,cnt,head[],x[],y[];
int dfn[],low[],vis[],hav[],bel[],q[];
struct edge{
int next,to;
}e[];
void insert(int u,int v){
cnt++;
e[cnt].next=head[u];e[cnt].to=v;
head[u]=cnt;
}
int top,ind,k;
void tarjan(int x){
q[++top]=x;
dfn[x]=low[x]=++ind;
vis[x]=;
for(int i=head[x];i;i=e[i].next){
int s=e[i].to;
if(!dfn[s]){
tarjan(s);
low[x]=min(low[s],low[x]);
}
else if(vis[s]){
low[x]=min(dfn[s],low[x]);
}
}
int now=;
if(dfn[x]==low[x]){
k++;
while(now!=x){
now=q[top];top--;
vis[now]=;
bel[now]=k;
hav[k]++;
}
}
}
int ans;
void work(){
for(int i=;i<=k;i++){
if(!head[i]){
if(ans){
ans=;
return ;
}
else ans=hav[i];
}
}
}
int mx=;
int main(){
scanf("%d%d",&n,&m);
int u,v,t;
for(int i=;i<=m;i++){
scanf("%d%d",&x[i],&y[i]);
insert(x[i],y[i]);
}
for(int i=;i<=n;i++){
if(!dfn[i])tarjan(i);
}
cnt=;
memset(head,,sizeof head);
memset(e,,sizeof e);
for(int i=;i<=m;i++){
if(bel[x[i]]!=bel[y[i]])insert(bel[x[i]],bel[y[i]]);
}
work();
printf("%d",ans);
return ;
}
最新文章
- 【Android群英传】学习笔记(二)
- hdu3247Resource Archiver(ac自动机+spfa)
- wpf 旋转效果
- linux后台开发排错常用工具
- 51nod 1413 权势二进制 背包dp
- C++、GDAL创建shapefile文件
- Windows 下 SVN 服务器配置
- BufferedInputStream
- 在SSMS里查看TDS数据包内容
- MySQLdb/mysql-python安装时EnvironmentError: mysql_config not found
- fetch使用的常见问题及解决办法
- ssh 免密钥失败原因
- 第四次java实验
- dreamware2018破解
- 线程(六)之LOCK和synchronized
- 这样好用的ReactiveCocoa,根本停不下来
- 2. Python3 基础入门
- underscore.js 分析6 map函数
- Alter GDG limit
- 360UI 界面框架 即QUI框架与EXT比较
热门文章
- Kettle的概念学习系列之Kettle是什么?(一)
- KafkaZookeeper1-整体介绍
- AndroidStudio EventBus报错解决方法its super classes have no public methods with the @Subscribe
- SpringBoot学习笔记(7)-----CORS支持解决跨域问题
- POJ-3660 Cow Contest Floyd传递闭包的应用
- POJ-2253 Frogger dijsktra查找间隔最小的路径
- 洛谷 P4147 玉蟾宫 (最大子矩形问题)
- Gitlab command line instructions
- Docker学习总结(10)——10分钟玩转Docker
- 赵雅智:android教学大纲