无向图双连通分量BCC（全网最好理解）

不是标题党，之前我也写过一篇比较全的，但是对于初学者不友好。传送门?

双连通分量（Biconnected component）：

1.边双联通 E-BCC

2.点双连通 V-BCC

双连通分量分为点双连通（V-BCC）和边双连通（E-BCC），这是图论学习中一个很重要的知识点，也是图的变形转化的一个主要方法。通过V-BCC缩点可以求割边（桥），也可以通过E-BCC缩点求割点。这是我们今天讲的主要的内容。

1.边双连通分量

先说不好理解的定义：若一个无向图的点两两间都有两条不重合的路径，那么我们就称这个无向图是边-双连通的。

我们看看这个定义又是什么意思，任意两点都有两条不重合的路径，就是说任意点都有两条边可以到达，那么任意去掉一条边，肯定还有另一条边连接，也就是说这个图中不存在割边。所以这个图是边双连通图。

我们画个图来理解：

这下来大家应该明白什么边双连通了，接下来讲边双连通分量（分支) 。

所谓分支就是一个子图，那么边双连通分支就是说原图中最大的一个双连通分支的子图。一定是最大不然会影响结果。比较好理解，直接上图。

这个图有两个双连通分量，边双连通分量，就是这么多内容。我们再讲讲边双连通分量缩点。

如果将双连通分支用一个点表示，那么就叫做E-DCC缩点。经过缩点后建的图必然不存双连通分量，图中存在的边都不在双连通分支中，也就是说缩点后的边都是桥。

2.点双连通分支

定义：任意两条边都在一个简单环中。

就是说没有割点。还是画图吧！

这两个最大连通子图就是点双联通分支，类比边双连通分支。

也就是说经过缩点后的图中的点除了只有一条边的的点都是割点。

我们下一期讲Tarjan算法求双连通分量。

巴特西