图的割点和桥
2026-08-19 19:27:43
发布于：广东
由于本蒟蒻过菜，本文有借鉴OIwiki进行编写
若大家想看OIwiki内容的话->传送门
割点
割点在OIwiki上的记载是：对于一个无向图，如果把一个点删除后这个图的极大连通分量数增加了，那么这个点就是这个图的割点（又称割顶）、
大家第一次看也可能看不懂，比如我，这里我给大家一个我自己认为比较通俗的翻译：
对于一个无向图，如果把一个点删除后这个图不连通了，那么这个点就是这个图的割点。
如下图：
有点抽象见谅，图中红点3、4就为这幅图的割点，因为把点3或4删去后，本图不能连通，因此点3、4为图的割点。
那如何求一个图的割点呢？
首先，我们按照 DFS 序给他打上时间戳（访问的顺序）。
这些信息被我们保存在一个叫做 dfn 的数组中。
还需要另外一个数组 low，用它来存储不经过其父亲能到达的最小的时间戳。
然后我们开始 DFS，我们判断某个点是否是割点的根据是：对于某个顶点 𝑢，如果存在至少一个顶点 𝑣（𝑢的儿子），使得 𝑙𝑜𝑤𝑣 ≥𝑑𝑓𝑛𝑢，即不能回到祖先，那么 𝑢 点为割点．
但是！！！，此结论不适用于搜索的起始点，需要特殊考虑：若该点不是割点，那么其他路径能到达全部结点，因此从起始点只「向下搜了一次」，就是在搜索树内仅有一个子结点．如果在搜索树内有两个及以上的儿子，那么他一定是割点了。如果只有一个儿子，那么把它删掉，不会有任何的影响．比如下面这个图，此处形成了一个环。
太懒了直接从OIwiki上搬了
（灰色表示现在暂先走另一条路）
我们在访问 1 的儿子时候，假设先 D（FS） 到了 2，然后标记用过，然后递归往下，来到了 4，4 又来到了 3，当递归回溯的时候，会发现 3 已经被访问过了，所以不是割点。
更新 low 的伪代码如下：
if v 是 u 的孩子 low[u]=min(low[u],low[v])
else low[u]=min(low[u],dfn[v])
例题
桥
和割点差不多。
割点在OIwiki上的记载是：对于一个无向图，如果删掉一条边后图中的连通分量数增加了，则称这条边为桥或者割边．严谨来说，就是：假设有连通图 𝐺 ={𝑉,𝐸} ，𝑒 是其中一条边（即 𝑒 ∈𝐸），如果 𝐺 −𝑒是不连通的，则边 𝑒 是图 𝐺 的一条割边（桥）
翻译：如果删掉一条边后导致整个图不连通，那么这条边就叫做桥
比如说，下图中：
链接3与4的那条红色边就叫桥
过程：和割点差不多，只要改成low_v>dfn_u 就可以了，而且不需要考虑根节点的问题．
割边和是不是根节点没有关系，原来我们求割点的时候是指点 v 是不可能不经过父节点 u 为回到祖先节点（包括父节点），所以顶点 u 是割点．如果 low_v=dfn_u 表示还可以回到父节点，如果顶点 v 不能回到祖先也没有另外一条回到父亲的路，那么 u-v 这条边就是割边．
下面代码可以实现这一效果
int low[MAXN], dfn[MAXN], idx;
bool bridge[MAXN];
vector<int> G[MAXN];
int bridge;
int father[MAXN];
void tarjan(int u, int fa){
father[u] = fa;
low[u] = dfn[u] = ++idx;
for(const auto &v : G[u]){
if(!dfn[v]){
tarjan(v, u);
low[u] = min(low[u], low[v]);
if(low[v] > dfn[u]){
bridge[v] = true;
++bridge;
}
}else if (v != fa){low[u] = min(low[u], dfn[v]);}
}
}
PS：这一代吗只能实现对无重边的无向图求割边，后续我会补上有重边的无向图求割边
再重申一遍：本蒟蒻十分菜鸡，如果各位dalao发现了我的文章中的问题，欢迎指正，谢谢大家
可以的话请各位吴彦祖点个赞谢谢
有帮助，赞一个