圆方树

What · 是什么

圆方树(Round-Square Tree / Block-Cactus Tree)是将无向图转化为树的一种结构：原图每个点对应一个圆点，每个点双连通分量对应一个方点，方点与它代表的点双中所有圆点连边。这样原图有n个点、c个点双时，圆方树有n+c个点(小于2n)，每条边连接一个圆点和一个方点。原图连通时圆方树是一棵树，否则是森林。圆方树的关键性质：两圆点在圆方树上的路径经过的方点+圆点集合，恰好对应原图中两点间所有简单路径并集上的点集。因此常把'简单路径必经/可达哪些点'类问题(如铁人两项、战略游戏、点权最值)转化为树上路径问题，用树链剖分/倍增LCA/树形DP求解。

Why · 为什么

How · 实现

伪代码

build(u, parent):
  dfn[u]=low[u]=++timer
  stk.push(u)
  for v in adj[u]:
    if not dfn[v]:
      build(v,u)
      low[u]=min(low[u],low[v])
      if low[v]==dfn[u]:      # u为点双的根
        cnt+=1                # 新建方点 cnt
        while stk.top()!=v:
          x=stk.pop()
          add_edge(cnt, x)    # 方点连圆点
        x=stk.pop(); add_edge(cnt, x)
        add_edge(cnt, u)      # u也连向方点, 但不弹出
    elif v!=parent:
      low[u]=min(low[u],dfn[v])

Python 实现

import sys

sys.setrecursionlimit(1 << 25)


def build_block_forest(n, adj):
    """构造圆方树.
    n: 原图点数(0-based), adj[u]=[v,...]
    return: (tree, square_start)
      tree: 圆方树邻接表 (0..n-1圆点, n.. 方点)
      square_start: 方点起始编号
    """
    dfn = [0] * n
    low = [0] * n
    timer = [0]
    stk = []
    tree = [[] for _ in range(2 * n)]
    sq_cnt = [n]

    def add(u, v):
        tree[u].append(v)
        tree[v].append(u)

    def tarjan(u):
        dfn[u] = low[u] = timer[0] = timer[0] + 1
        stk.append(u)
        for v in adj[u]:
            if not dfn[v]:
                tarjan(v)
                low[u] = min(low[u], low[v])
                if low[v] == dfn[u]:  # u是该点双的根
                    sq = sq_cnt[0]
                    sq_cnt[0] += 1
                    while True:
                        x = stk.pop()
                        add(sq, x)
                        if x == v:
                            break
                    add(sq, u)  # u不弹出, 也连方点
            else:
                low[u] = min(low[u], dfn[v])

    for s in range(n):
        if not dfn[s]:
            tarjan(s)
    return tree, n


if __name__ == "__main__":
    # 测试: 环 0-1-2-0 (一个点双) + 2-3 (单边, 一个点双)
    # 点双: {0,1,2} 和 {2,3}, 割点 2
    # 圆方树: 先触发方点4(点双{2,3}), 再触发方点5(点双{0,1,2})
    adj = [[] for _ in range(4)]
    for u, v in [(0, 1), (1, 2), (2, 0), (2, 3)]:
        adj[u].append(v)
        adj[v].append(u)
    tree, _ = build_block_forest(4, adj)
    # 统计方点(编号>=4)
    squares = [i for i in range(len(tree)) if i >= 4 and tree[i]]
    assert squares == [4, 5], squares
    # 方点4连2,3; 方点5连0,1,2
    assert set(tree[4]) == {2, 3}, tree[4]
    assert set(tree[5]) == {0, 1, 2}, tree[5]
    # 边数 = 圆点数+方点数-1(连通树) = 4+2-1=5
    edge_count = sum(len(x) for x in tree) // 2
    assert edge_count == 5, edge_count

    # 简单链 0-1-2: 每个点双为单边, 三个方点, 圆方树即原树
    adj2 = [[] for _ in range(3)]
    for u, v in [(0, 1), (1, 2)]:
        adj2[u].append(v)
        adj2[v].append(u)
    tree2, _ = build_block_forest(3, adj2)
    edge2 = sum(len(x) for x in tree2) // 2
    assert edge2 == 4, edge2  # 3圆点+2方点, 树边=5-1=4

    print("block-forest: ALL TESTS PASSED")

易错点

• 数组要开2n以上(圆方树点数<2n), 开小会越界
• 弹栈到v为止且u不弹出: u作为割点属于多个点双
• low[v]==dfn[u]才触发建方点(与割点判定low[v]>=dfn[u]不同, 与桥判定low[v]>dfn[u]更不同)
• 查询路径最值时若LCA是方点需额外取LCA父亲圆点的权
• 图不连通时是圆方森林, 需按连通块处理

例题

信源

• OI Wiki✓ https://oi-wiki.org/graph/block-forest/
• Wikipedia✓ https://en.wikipedia.org/wiki/Biconnected_component