USACO06JAN The Cow Prom /// tarjan求强联通分量 oj24219
2024-09-06 07:07:59
题目大意:
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 ;
}
最新文章
- qq空间等闪动的文字怎么做?
- [C/C++基础] C语言常用函数sprintf和snprintf的使用方法
- C基础之递归(思想很重要,学会找规律)
- 将request.getParameterMap()转换成可操作的普通Map
- 第六篇 SQL Server代理深入作业步骤工作流
- 表结构导出到excel中
- @Resource注解
- 如何初始化一个iOS原生地图
- C++中联合体(union)的使用
- CouchDB简单应用
- 利用jquery实现电商网站常用特效之:五星评分
- ZKClient操作zookeeper
- [vue]mvc模式和mvvm模式及vue学习思路(废弃)
- CentOS 7 时间, 日期设置 (含时间同步)
- Boosting
- windows7 asp.net发布IIS 拒绝访问 解决方法
- Ubuntu14.04下hadoop-2.6.0单机配置和伪分布式配置
- mysql 怎么给一个表一次增加多个字段, mysql 添加 多个 字段
- Mysql之select
- PIE SDK Command&;&;Tool工具命令一览表
热门文章
- go语言将函数作为参数传递
- 13、java获取路径
- pta作业1
- 20140729 while((*pa++=*pb++)!=&#39;\0&#39;) 合并数组代码 C++类型转换关键字 封装 多态 继承
- 20140604 word表格中打钩 循环右移
- 列表分成N等份
- python全栈开放实践第三版第一章的练习题完成情况
- undefined reference to `TTF_Init&#39;
- 判断字符串是否为JSON
- 从零开始搭建系统1.4——MySql安装及配置