首页 > 代码库 > 无向图的割顶和桥
无向图的割顶和桥
割顶： 关键点，删掉这个点后，图的连通分量 + 1；
桥： 在割顶的基础上，发现删除 (u,v) 这条边，图就变成非连通的了。
如何找出所有割顶和桥：
时间戳： 在无向图的基础上，DFS建树的过程中，各点进栈和出栈的时间 dfs_clock，进栈的时间 pre[]，出栈的时间 post[]
在DFS程序中的体现就是：
void previst(int u) { pre[u]= ++dfs_clock; }
void postvist(int u) { post[u] = ++dfs_clock; }
如何求割顶和桥 (定理)：
通过无向图建DFS森林后，每个点 u 是割顶的充要条件 ： u 存在一个子节点 v ，使得 v 或者其子孙结点 没有一条返回边到 u 的祖先。
实现：
low(u) : u 及其 子孙结点能返回的 最早的祖先的 pre 值，那么定理就可以写成 low(v) >=pre[u];
特殊情况：当 v 的 后代 只能连回自己，即 low(v) > pre[u] 时，删掉这条边 (u,v) 就变成非连通的了，这条边就是 桥.
代码：
#include <bits/stdc++.h>using namespace std;const int MaxNode = 1000;int pre[MaxNode<<1];int post[MaxNode<<1];vector <int> G[MaxNode];int iscut[MaxNode];int low[MaxNode];int dfs_clock;int dfs(int u,int fa) { int lowu = pre[u] = ++dfs_clock; int child = 0; for(int i=0;i<G[u].size();i++) { int v = G[u][i]; if(!pre[v]) { child ++; int lowv = dfs(v,u); if(lowv>=pre[u]) { iscut[u] = true; } } else if(pre[v]<pre[u]&&v!=fa) { lowu = min(lowu,pre[v]); } } if(fa<0&&child==1) iscut[u] = 0; low[u] = lowu; return lowu;}
注意：
无向图的边会处理两次，而在 DFS 树中 可能访问已经访问过的结点，可以利用这个结点更新 low 函数，但是 这个结点一定不能是 u 的父亲.
无向图的割顶和桥
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。