Tarjan-割点
2024-09-01 17:09:11
割点——tarjan
#include <bits/stdc++.h> using namespace std; ; ; int n, m; int ans;//个数 * MAXM], nxt[ * MAXM]; void add(int x, int y) { nxt[++cnt] = head[x]; head[x] = cnt; v[cnt] = y; } int dfn[MAXN], low[MAXN], ind; int cut[MAXN]; void tarjan(int now, int fa) { dfn[now] = low[now] = ++ind; ; for (int i = head[now]; i ; i = nxt[i]) { if(!dfn[v[i]]) { tarjan(v[i], now); low[now] = min(low[now], low[v[i]]); ;//不为根节点 if(now == fa) child++; //为根节点,子树统计 } else { low[now] = min(low[now], dfn[v[i]]); } } ) cut[now] = ;//为根节点且有两个及以上的子节点 } int main() { scanf("%d%d", &n, &m); ; i <= m; i++) { int x, y; scanf("%d%d", &x, &y); add(x, y); add(y, x); } ; i <= n; i++) if(!dfn[i]) tarjan(i, i); ; i <= n; i++) ) ans++; printf("%d\n", ans); ; i <= n; i++) ) printf("%d ", i); ; }
最新文章
- Eclipse 设置SVN忽略文件
- Azure ARM (10) ARM模式下的虚拟机和Classic Model虚拟机的区别
- spring + myBatis 常见错误:注解事务不回滚
- Escape Sequences
- js数组内置方法
- UILabel 自动换行 和支持换行符
- WPF——传实体类
- Cocos2d-x 3.1.1 学习日志4--cocos2d-x解决中文乱码问题的几种办法
- Windows漏洞利用与防护(2015.8)
- Valgrind使用记录
- Java环境变量,真的还有必要配吗?
- privoxy自动请求转发到多个网络
- js模拟ctrl+c的问题
- Golang的排序和查找
- R的极客理想系列文章--转载
- Oracle EBS GL总账凭证取值
- mac 无法验证副本
- Elasticsearch 知识点
- 笔记本的Windows系统怎么设置有了外接鼠标后停用触摸板
- test20181024 zi