$割点割顶tarjan$
2024-09-30 18:41:26
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
inline LL read () {
LL res = ;
int f () ;
char ch = getchar ();
while (!isdigit(ch)) {
if (ch == '-') f = - ;
ch = getchar();
}
while (isdigit(ch)) res = (res << ) + (res << ) + (ch ^ ),ch = getchar();
return res * f ;
}
const int N = +;
int a[N] , nxt [N] , head[N] , dfn[N] , low[N] , cnt , k ;
bool cut[N] , bst[N] ;
inline void Add (int x ,int y) {
a[++k] = y ; nxt[k] = head[x]; head[x] = k ; return ;
}
inline void tarjan (int u,int mr) {
int rc = ;
dfn[u] = low[u] = ++ cnt ;
for ( register int p = head[u] ; p ; p = nxt[p] ) {
int v = a[p] ;
if (! dfn [v]) {
tarjan ( v , mr ) ;
low[u] = min ( low[u] , low[v] );
if (low[v] >= dfn[u] and u != mr) cut[u]=true;
if (u == mr) rc ++ ;
}
low[u] = min ( low[u] , dfn[v] ) ;
}
if (u == mr and rc >= ) cut[mr] = true;
}
signed main() {
int n = read() ;
int m = read() ;
int ans = ;
for ( register int i = ;i <= m ; i ++) {
int x = read() ;
int y = read() ;
Add (x,y) ; Add (y,x) ;
}
for ( register int i = ;i <= n ; i ++)
if ( ! dfn[i] ) tarjan ( i , i ) ;
for ( register int i = ;i <= n ; i ++)
if ( cut[i] ) ans ++ ;
cout << ans << endl ;
for ( register int i = ;i <= n ; i ++)
if ( cut[i] ) cout << i << ' ' ;
return ;
}
首先tarjan求割点的重点就是dfn和low数组的理解。
dfn[i]就是时间戳,即在什么时刻搜索到了点i,
low[i]则是i点能回溯到的dfn最小的祖先,
搜索的时候判断一下当对于点x存在儿子节点y,使得dfn[x]<=low[y]则x一定是割点。
因为只要x的子节点不能回溯到x的上面,就是没有返祖边超过x点,那么割掉x就能造成不连通了
好啦,基本算法介绍完,就要讲几个问题了。
首先,为什么此处
low[a]=min(low[a],dfn[p]);
不能写作
low[a]=min(low[a],low[p]);
在我的理解,由于此处是一张无向图,我们有双向建了边,导致节点可以回溯到它的父节点;
而如果从它的父节点或其父节点的另一棵子树上有向上很多的返祖边,
这时把子节点的low值赋为父节点的low,就可能导致其low==其父节点low<其父节点dfn,
从而使本该是割点的点被忽视了,答案就少了,所以就wa了。
另外本题还有几个注意点:
给的图不一定是连通图,即求每个联通块的割顶
输出格式别看错了2333
链式前向星开边要2倍
最新文章
- 整理分享原生态mac AndroidStudio的快捷键
- (转)dubbo框架基本分析
- python扩展实现方法--python与c混和编程 转自:http://www.cnblogs.com/btchenguang/archive/2012/09/04/2670849.html
- SpringHttpInvoker解析3-客户端实现
- Getting the first day in a week with T-SQL
- Xcode如何打包ipa安装包
- 5月11日 ArrayList集合复习、特殊集合、枚举类型
- 如何将两个列表变成一个python字典
- .gitignore的使用:首次创建及事后添加无法生效.
- poj3261 Milk Patterns(后缀数组)
- Android ListView 常见问题与使用总结
- 右键打开cmd命令出错
- [C#]200 行代码使用 C# 实现区块链
- 基于注解处理器开发自动生成getter和setter方法的插件
- jquery或者JavaScript调用WCF服务的方法
- phpcms v9模板制作常用代码集合(转)
- <;c:out />;的理解
- POJ1459:Power Network(dinic)
- Redis客户端基本命令
- 阅读android源码了解 android 加载so的流程