图的连通 (2)

8.3 找出双连通元件

图 G 上面的双连通元件 (Biconnected Component) 是指，一个极大的子图，使得该子图内不存在关节点。
经过一些有趣的证明以後，可以知道图 G 上的每一条边，至多属於一个双连通元件。
但是，同一个点可能分属多个双连通元件。因此，如果要找出双连通元件，得把边分成很多等价类来下手。

由於每一个点可能属於许多双连通元件，我们可以用一个点来代表双连通元件、而将双连通元件与接触到的割点以边连起来。连起来以後可以证明它会形成一棵树，而这样的树我们称为 BC树 (Block-Cut Tree)。

要怎麽找出双连通元件呢？一个可行的演算法如下：首先找一棵生成树，接着，对於每一条不是树上的边 (u, v)，都可以在树上找一条路径，形成一个环，这个环通常称为 fundamental cycle。简单来说，这个环上所有的边，都属於同一个双连通元件。因此，我们可以用并查集(或甚至是全部记录下来以後跑一次 DFS) 把双连通元件里面的边都合并起来，就能得到要得结果啦。

8.4 耳分解 Ear Decomposition

还有另外一种建构双连通图的方式：从一个圈开始，然後每一次挑两个点，额外增加一条路径。如果这两个点允许是同一个点，那麽这个耳分解生出来的图是 2-边连通的(即拿掉一条边，图仍然是连通的，但可能拿掉点就会不连通了)。如果每次挑选的两个点都是相异的点，那这个耳分解又被称为开耳分解 (open ear decomposition)。