前言
在图论中，除了在有向图中的强连通分量，在无向图中还有一类双连通分量
双连通分量一般是指点双连通分量
当然，还有一种叫做边双连通分量
点双连通分量
对于一个连通图，如果任意两点至少存在两条“点不重复”的路径，则说图是点双连通的（即任意两条边都在一个简单环中），点双连通的极大子图称为点双连通分量。
计算方法比较简单
在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)个孩子时才是割点。
例题
内容来源于网络如有侵权请私信删除
- 还没有人评论，欢迎说说您的想法！
客服
