点双连通分量与割点
程序员文章站
2022-04-15 20:05:24
前言 在图论中,除了在有向图中的强连通分量,在无向图中还有一类双连通分量 双连通分量一般是指 点双连通分量 当然,还有一种叫做 边双连通分量 点双连通分量 对于一个连通图,如果任意两点至少存在两条“点不重复”的路径,则说图是点双连通的(即任意两条边都在一个简单环中),点双连通的极大子图称为点双连通分 ......
前言
在图论中,除了在有向图中的强连通分量,在无向图中还有一类双连通分量
双连通分量一般是指点双连通分量
当然,还有一种叫做边双连通分量
点双连通分量
对于一个连通图,如果任意两点至少存在两条“点不重复”的路径,则说图是点双连通的(即任意两条边都在一个简单环中),点双连通的极大子图称为点双连通分量。
计算方法比较简单
在tarjan的过程中,如果由\(i\) dfs到\(j\),并且\(low[j]>=dfn[i]\),那么进行弹栈直到\(j\)被弹出,弹出的点加上\(i\)构成了一个点双连通分量。
(实际就是在搜索树种这个点和它下面的点构成了一个双连通分量)
注意在tarjan的过程中,我们可以选择存边,也可以存点,不过存点的话边界条件要变一下
do { h=s.top();s.pop(); #¥%……&*(() }while(h!=edge[i].v);//warning
与二分图的关系
(1) 如果一个点双连通分量内的某些顶点在一个奇圈中(即双连通分量含有奇圈),那么这个双连通分量的其他顶点也在某个奇圈中;
(2) 如果一个点双连通分量含有奇圈,则他必定不是一个二分图。反过来也成立,这是一个充要条件。
例题
割点(割顶)
割点:对于无向图中的点\(i\),若去掉\(i\)点,无向图的连通快个数会增加,则称点\(i\)为割点
不难发现一个点是割点当且仅当他在多个点双里。
考虑之前求点双的过程,找到一个点双时,那个\(i\)就是一个割点。
根节点需要特判一下,必须要有至少\(2\)个孩子时才是割点。
例题
推荐阅读
-
图论小结(一)包括一些最短路,最小生成树,差分约束,欧拉回路,的经典题和变种题。强连通,双连通,割点割桥的应用。二分匹配
-
点双连通分量与割点
-
图论小结(一)包括一些最短路,最小生成树,差分约束,欧拉回路,的经典题和变种题。强连通,双连通,割点割桥的应用。二分匹配
-
1027 - Tarjan之点双连通分量 - 矿场搭建[HNOI2012]
-
UOJ#30/Codeforces 487E Tourists 点双连通分量,Tarjan,圆方树,树链剖分,线段树
-
Bubble Cup 11 - Finals [Online Mirror, Div. 2] B. Hyperspace Highways(tarjan - 点双连通分量 + LCA)
-
点双连通分量与割点