bzoj1654 / P2863 [USACO06JAN]牛的舞会The Cow Prom
2024-10-18 01:57:16
P2863 [USACO06JAN]牛的舞会The Cow Prom
求点数$>1$的强连通分量数,裸的Tanjan模板。
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int min(int &a,int &b){return a<b?a:b;}
#define N 10002
#define M 50002
int n,m,clo,dfn[N],low[N],blo,be[N],tp,st[N],ans;
int cnt,hd[N],nxt[M<<],ed[N],poi[M<<];
void adde(int x,int y){
nxt[ed[x]]=++cnt; hd[x]=hd[x]?hd[x]:cnt;
ed[x]=cnt; poi[cnt]=y;
}
void tarjan(int x){
dfn[x]=low[x]=++clo; st[++tp]=x;
for(int i=hd[x];i;i=nxt[i]){
int to=poi[i];
if(!dfn[to]){
tarjan(to);
low[x]=min(low[x],low[to]);
}else if(!be[to]) low[x]=min(low[x],dfn[to]);
}
if(dfn[x]<=low[x]){
int tot=;
be[x]=++blo;
while(st[tp]!=x) be[st[tp--]]=blo,++tot;
--tp; ans+=(tot>);
}
}
int main(){
scanf("%d%d",&n,&m);
for(int i=,q1,q2;i<=m;++i)
scanf("%d%d",&q1,&q2),adde(q1,q2);
for(int i=;i<=n;++i) if(!dfn[i]) tarjan(i);
printf("%d",ans);
return ;
}
最新文章
- ABP源码分析十六:DTO的设计
- PHP 模拟POST请求
- PHP函数之日期时间函数date()使用详解
- comet4j文档
- Android Studio--学习系列(1)
- linux内核空间与用户空间信息交互方法
- NGUI HUDText
- Linux通过防火墙禁止IP来防止攻击
- jquery的2.0.3版本源码系列(1)总体结构
- [Redis源码阅读]dict字典的实现
- Android利用RecyclerView实现列表倒计时效果
- pycharm的快捷键
- Unicode vs. UTF-8 etc.
- msfconlose基本命令
- 2017-2018-2 20165325 实验四《Android程序设计》实验报告
- BarTender怎样同时打印自动日期和流水号?
- 在phpstorm中svn的使用
- vue接口地址配一个全局的
- 漂亮的圆角文本框 CSS3实现
- The Hard Thing About Hard Things
热门文章
- 从UE(用户体验)到道家誓学再到李小龙
- iOS-数据缓存(转载)
- 使用 SendARP 获取 MAC 地址(使用SendARP API函数,很多相关文章)
- Win10系统 Eclipse 下&#39;Publishing to Tomcat&#39;has encountered a problem解决办法
- mysql 权限管理 针对表的字段 级别 授权 columns_priv表
- 下厨房6月26日数据丢失事故总结 MYSQL主分区被rm 命令误删除
- MySQL中MyISAM与InnoDB区别及选择,mysql添加外键
- AMR格式语音采集/编码/转码/解码/播放
- Javaweb开发请求
- PAT Counting Leaves[一般]