前置知识:点双连通分量,简称点双。
一个点双内任意两点之间存在至少两条简单路径,即点双内不存在割点。
一个点可能属于多个点双,但一条边恰好属于一个点双。
求出点双之后我们做一个类似于缩点的东西,钦定圆点表示原图中的点,方点表示缩点后的一个点双。
构建一棵圆方树,只需要把每个点双对应的方点向内部所有圆点连边即可。
因此设原图有 $n$ 个点,有 $k$ 个点双,则圆方树有 $n+k \leq 2n$ 个点,数组要开两倍!!
偷一下 OI-Wiki 的图。
那话说回来为什么要把图构造成树呢??
显然树有很多优美的性质,可以通过各种 DS 维护信息,但图就相对复杂很难维护。
猜你想问:为什么我要学圆方树?
qwq
$$\Huge Coding…$$
顺带一提点双的缩点。
由于一个割点可能属于多个点双,所以需要保留这些割点,并向它们所属的点双连边。