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