传送门

有向图,找点数大于1的强连通分量个数

——代码

 #include <stack>
#include <cstdio>
#include <cstring>
#include <iostream> const int MAXN = ;
int n, m, cnt, idx, size, ans;
int head[MAXN], to[MAXN << ], next[MAXN << ];
int dfn[MAXN], low[MAXN], belong[MAXN], tot[MAXN];
bool ins[MAXN];
std::stack <int> s; inline int read()
{
int x = , f = ;
char ch = getchar();
for(; !isdigit(ch); ch = getchar()) if(ch == '-') f = -;
for(; isdigit(ch); ch = getchar()) x = (x << ) + (x << ) + ch - '';
return x * f;
} inline int min(int x, int y)
{
return x < y ? x : y;
} inline void add(int x, int y)
{
to[cnt] = y;
next[cnt] = head[x];
head[x] = cnt++;
} inline void dfs(int u)
{
int i, v;
s.push(u);
ins[u] = ;
dfn[u] = low[u] = ++idx;
for(i = head[u]; i ^ -; i = next[i])
{
v = to[i];
if(!dfn[v])
{
dfs(v);
low[u] = min(low[u], low[v]);
}
else if(ins[v]) low[u] = min(low[u], dfn[v]);
}
if(low[u] == dfn[u])
{
size++;
do
{
v = s.top();
s.pop();
ins[v] = ;
belong[v] = size;
}
while(u ^ v);
}
} int main()
{
int i, x, y;
n = read();
m = read();
memset(head, -, sizeof(head));
for(i = ; i <= m; i++)
{
x = read();
y = read();
add(x, y);
}
for(i = ; i <= n; i++)
if(!dfn[i])
dfs(i);
for(i = ; i <= n; i++) tot[belong[i]]++;
for(i = ; i <= size; i++)
if(tot[i] > )
ans++;
printf("%d\n", ans);
return ;
}

最新文章

  1. mac 下设置jdk 路径,设置hadoop 路径
  2. 无法在web服务器上启动调试。Microsoft Visual Studio 远程调试监视器(MSVSMON.EXE)似乎没有在远程计算机上运行,VS2012调试错误
  3. jqGrid(struts2+jdbc+jsp)增删改查的例子
  4. asp.net mvc 用Redis实现分布式集群共享Session。
  5. UITableView实现格瓦拉飞天投票模块
  6. C#反射机制详解(转)
  7. Spring Boot中使用Swagger2构建API文档
  8. Git相关操作三
  9. python模板:自动化执行测试函数
  10. 在python3中安装mysql扩展,No module named &#39;ConfigParser&#39;
  11. http协议中的响应代码从 1xx ~ 5xx,一共有41种
  12. 20165223 week2学习查漏补缺
  13. DotNet 资源大全中文版
  14. git提交本地分支到远程分支
  15. 我的Netty笔记
  16. python multiprocessing 和tcp
  17. OpenDigg iOS开源项目月报201704
  18. Java第三阶段学习(八:网络通信协议、UDP与TCP协议)
  19. en笔记音标
  20. C++泛型和算法

热门文章

  1. bzoj 3498: PA2009 Cakes【瞎搞】
  2. linux编译安装gcc5.3.0
  3. JDK API文档下载
  4. WCF学习笔记(1)-一个完整的例子
  5. MySQL客户端导入数据库脚本,字段值出现乱码解决方法
  6. SpringMvc下的文件上传
  7. BZOJ1499: [NOI2005]瑰丽华尔兹(dp)
  8. 微软MVC框架实战:开源的JS库Knockout
  9. STL容器的排序
  10. 梦想Android版CAD控件2019.01.23更新