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 ;
}

最新文章

  1. ABP源码分析十六:DTO的设计
  2. PHP 模拟POST请求
  3. PHP函数之日期时间函数date()使用详解
  4. comet4j文档
  5. Android Studio--学习系列(1)
  6. linux内核空间与用户空间信息交互方法
  7. NGUI HUDText
  8. Linux通过防火墙禁止IP来防止攻击
  9. jquery的2.0.3版本源码系列(1)总体结构
  10. [Redis源码阅读]dict字典的实现
  11. Android利用RecyclerView实现列表倒计时效果
  12. pycharm的快捷键
  13. Unicode vs. UTF-8 etc.
  14. msfconlose基本命令
  15. 2017-2018-2 20165325 实验四《Android程序设计》实验报告
  16. BarTender怎样同时打印自动日期和流水号?
  17. 在phpstorm中svn的使用
  18. vue接口地址配一个全局的
  19. 漂亮的圆角文本框 CSS3实现
  20. The Hard Thing About Hard Things

热门文章

  1. 从UE(用户体验)到道家誓学再到李小龙
  2. iOS-数据缓存(转载)
  3. 使用 SendARP 获取 MAC 地址(使用SendARP API函数,很多相关文章)
  4. Win10系统 Eclipse 下&#39;Publishing to Tomcat&#39;has encountered a problem解决办法
  5. mysql 权限管理 针对表的字段 级别 授权 columns_priv表
  6. 下厨房6月26日数据丢失事故总结 MYSQL主分区被rm 命令误删除
  7. MySQL中MyISAM与InnoDB区别及选择,mysql添加外键
  8. AMR格式语音采集/编码/转码/解码/播放
  9. Javaweb开发请求
  10. PAT Counting Leaves[一般]