题目大意:

n个点 m条边的图 求大小大于1的强联通分量的个数

https://www.cnblogs.com/stxy-ferryman/p/7779347.html

tarjan求完强联通分量并染色后

计算一下每种颜色的个数 就是每个强联通块的大小

#include <stdio.h>
#include <cstring>
#include <algorithm>
#include <stack>
using namespace std; const int N=;
struct EDGE { int to, nt; }e[*N];
int head[N], tot;
int dfn[N], low[N], ind;
int col[N], id;
bool vis[N];
stack <int> s; int n, m, cnt[N]; void init() {
while(!s.empty()) s.pop();
for(int i=;i<=n;i++) {
head[i]=dfn[i]=low[i]=col[i]=-;
vis[i]=cnt[i]=;
}
tot=ind=id=;
}
void addE(int u,int v) {
e[tot].to=v;
e[tot].nt=head[u];
head[u]=tot++;
} void tarjan(int u) {
dfn[u]=low[u]=ind++;
s.push(u); vis[u]=;
for(int i=head[u];i!=-;i=e[i].nt) {
int v=e[i].to;
if(dfn[v]==-) {
tarjan(v);
low[u]=min(low[u],low[v]);
} else {
if(vis[v]) low[u]=min(low[u],low[v]);
}
}
if(dfn[u]==low[u]) {
col[u]=++id;
vis[u]=;
while(s.top()!=u) {
col[s.top()]=id;
vis[s.top()]=;
s.pop();
} s.pop();
}
} int main()
{
while(~scanf("%d%d",&n,&m)) {
init();
for(int i=;i<=m;i++) {
int u,v;
scanf("%d%d",&u,&v);
addE(u,v);
}
for(int i=;i<=n;i++)
if(dfn[i]==-) tarjan(i);
for(int i=;i<=n;i++)
cnt[col[i]]++;
int ans=;
for(int i=;i<=id;i++)
if(cnt[i]>) ans++;
printf("%d\n",ans);
} return ;
}

最新文章

  1. qq空间等闪动的文字怎么做?
  2. [C/C++基础] C语言常用函数sprintf和snprintf的使用方法
  3. C基础之递归(思想很重要,学会找规律)
  4. 将request.getParameterMap()转换成可操作的普通Map
  5. 第六篇 SQL Server代理深入作业步骤工作流
  6. 表结构导出到excel中
  7. @Resource注解
  8. 如何初始化一个iOS原生地图
  9. C++中联合体(union)的使用
  10. CouchDB简单应用
  11. 利用jquery实现电商网站常用特效之:五星评分
  12. ZKClient操作zookeeper
  13. [vue]mvc模式和mvvm模式及vue学习思路(废弃)
  14. CentOS 7 时间, 日期设置 (含时间同步)
  15. Boosting
  16. windows7 asp.net发布IIS 拒绝访问 解决方法
  17. Ubuntu14.04下hadoop-2.6.0单机配置和伪分布式配置
  18. mysql 怎么给一个表一次增加多个字段, mysql 添加 多个 字段
  19. Mysql之select
  20. PIE SDK Command&amp;&amp;Tool工具命令一览表

热门文章

  1. go语言将函数作为参数传递
  2. 13、java获取路径
  3. pta作业1
  4. 20140729 while((*pa++=*pb++)!=&#39;\0&#39;) 合并数组代码 C++类型转换关键字 封装 多态 继承
  5. 20140604 word表格中打钩 循环右移
  6. 列表分成N等份
  7. python全栈开放实践第三版第一章的练习题完成情况
  8. undefined reference to `TTF_Init&#39;
  9. 判断字符串是否为JSON
  10. 从零开始搭建系统1.4——MySql安装及配置