圆方树

在阅读下列内容之前，请务必了解

相关阅读：

引入

众所周知，树（或森林）有很好的性质，并且容易通过很多常见数据结构维护。

而一般图则没有那么好的性质，所幸有时我们可以把一般图上的某些问题转化到树上考虑。

而圆方树（Block forest 或 Round-square tree）¹就是一种将图变成树的方法。本文将介绍圆方树的构建，性质和一些应用。

限于篇幅，本文中有一些结论未经证明，读者可以自行理解或证明。

定义

圆方树最初是处理「仙人掌图」（每条边在不超过一个简单环中的无向图）的一种工具，不过发掘它的更多性质，有时我们可以在一般无向图上使用它。

要介绍圆方树，首先要介绍 点双连通分量。

一个 点双连通图 的一个定义是：图中任意两不同点之间都有至少两条点不重复的路径。
点不重复既指路径上点不重复（简单路径），也指两条路径的交集为空（当然，路径必然都经过出发点和到达点，这不在考虑范围内）。

可以发现对于只有一个点的图比较难定义它是不是一个点双，这里先不考虑节点数为 的图。

一个近乎等价的定义是：不存在割点的图。
这个定义只在图中只有两个点，一条连接它们的边时失效。它没有割点，但是并不能找到两条不相交的路径，因为只有一条路径。
（也可以理解为那一条路径可以算两次，的确没有交，因为不经过其他点）

虽然原始的定义的确是前者，但是为了方便，我们规定点双图的定义采用后者。

而一个图的 点双连通分量 则是一个 极大点双连通子图。
与强连通分量等不同，一个点可能属于多个点双，但是一条边属于恰好一个点双（如果定义采用前者则有可能不属于任何点双）。

在圆方树中，原来的每个点对应一个 圆点，每一个点双对应一个 方点。
所以共有 个点，其中 是原图点数， 是原图点双连通分量的个数。

而对于每一个点双连通分量，它对应的方点向这个点双连通分量中的每个点连边。
每个点双形成一个“菊花图”，多个“菊花图”通过原图中的割点连接在一起（因为点双的分隔点是割点）。

显然，圆方树中每条边连接一个圆点和一个方点。

下面的图显示了一张图对应的点双和圆方树形态。²

圆方树的点数小于 ，这是因为割点的数量小于 ，所以请注意各种数组大小要开两倍。

其实，如果原图连通，则“圆方树”才是一棵树，如果原图有 个连通分量，则它的圆方树也会形成 棵树形成的森林。

如果原图中某个连通分量只有一个点，则需要具体情况具体分析，我们在后续讨论中不考虑孤立点。

过程

对于一个图，如何构造出它的圆方树呢？首先可以发现如果图不连通，可以拆分成每个连通子图考虑，所以我们只考虑连通图。

因为圆方树是基于点双连通分量的，而点双连通分量又基于割点，所以只需要用类似求割点的方法即可。

求割点的常用算法是 Tarjan 算法，如果你会了理解下面的内容就很简单了，如果你不会也没关系。

我们跳过 Tarjan 求割点，直接介绍圆方树使用的算法（其实是 Tarjan 的变体）：

对图进行 DFS，并且中间用到了两个关键数组 dfn 和 low（类似于 Tarjan）。

dfn[u] 存储的是节点 的 DFS 序，即第一次访问到 时它是第几个被访问的节点。
low[u] 存储的是节点 的 DFS 树中的子树中的某个点 通过 最多一次返祖边或向父亲的树边 能访问到的点的 最小 DFS 序。
如果没有听说过 Tarjan 算法可能会有点难理解，让我们举个例子吧：

（可以发现这张图其实和上面图片中的图等价）
这里树边从上至下用直线画出，返祖边从下至上用曲线画出。节点的编号便是它的 DFS 序。

则有 low 数组如下：

并不是很难理解吧，注意这里 的 low 是 ，与一些求割点的做法有差异，因为为了方便，我们规定了可以通过父边向上，但主要思想是相同的。

我们可以很容易地写出计算 dfn 和 low 的 DFS 函数（初始时 dfn 数组清零）：

```cpp
void Tarjan(int u) {
  low[u] = dfn[u] = ++dfc;                // low 初始化为当前节点 dfn
  for (int v : G[u]) {                    // 遍历 u 的相邻节点
    if (!dfn[v]) {                        // 如果未访问过
      Tarjan(v);                          // 递归
      low[u] = std::min(low[u], low[v]);  // 未访问的和 low 取 min
    } else
      low[u] = std::min(low[u], dfn[v]);  // 已访问的和 dfn 取 min
  }
}
```

```python
def Tarjan(u):
    low[u] = dfn[u] = dfc # low 初始化为当前节点 dfn
    dfc = dfc + 1
    for v in G[u]: # 遍历 u 的相邻节点
        if dfn[v] == False: # 如果未访问过
            Tarjan(v) # 递归
            low[u] = min(low[u], low[v]) # 未访问的和 low 取 min
        else:
            low[u] = min(low[u], dfn[v]) # 已访问的和 dfn 取 min
```

接下来，我们考虑点双和 DFS 树以及这两个数组之间的关联。

可以发现，每个点双在 DFS 树上是一棵连通子树，并至少包含两个点；特别地，最顶端节点仅往下接一个点。

同时还可以发现每条树边恰好在一个点双内。

我们考虑一个点双在 DFS 树中的最顶端节点 ，在 处确定这个点双，因为 的子树包含了整个点双的信息。

因为至少有两个点，考虑这个点双的下一个点 ，则有 ， 之间存在一条树边。

不难发现，此时一定有 。
更准确地说，对于一条树边 ， 在同一个点双中，且 是这个点双中深度最浅的节点 当且仅当 。

那么我们可以在 DFS 的过程中确定哪些地方存在点双，但是还不能准确确定一个点双所包含的点集。

这并不难处理，我们可以在 DFS 过程中维护一个栈，存储还未确定所属点双（可能有多个）的节点。

在找到点双时，点双中除了 以外的其他的点都集中在栈顶端，只需要不断弹栈直到弹出 为止即可。

当然，我们可以同时处理被弹出的节点，只要将其和新建的方点连边即可。最后还要让 和方点连边。

这样就很自然地完成了圆方树的构建，我们可以给方点标号为 开始的整数，这样可以有效区分圆点和方点。

这部分可能讲述得不够清晰，下面贴出一份代码，附有详尽注释以及帮助理解的输出语句和一份样例，建议读者复制代码并自行实践理解，毕竟代码才是最能帮助理解的（不要忘记开 c++11）。

提供一个测试用例：

13 15
1 2
2 3
1 3
3 4
3 5
4 5
5 6
4 6
3 7
3 8
7 8
7 9
10 11
11 10
11 12

这个例子对应的图（包含了重边和孤立点的情况）：

例题

我们讲一些可以使用圆方树求解的例题。

外部链接

immortalCO，圆方树——处理仙人掌的利器，Universal OJ。

参考资料与注释