[圆方树学习笔记]

这周要期中考了,好难受。
趁体育课来机房学一会。
在我市三个队爷的博客里找题做。/wq
找到队爷们学圆方树的题,刚好不会这个,来学一下。

首先要明白什么叫点双联通分量。
原始定义为:图中任意两不同点之间都有至少两条点不重复的路径。
近乎定价的一个定义:图中不存在割点。
两者的差别为:两个点一条边是否算作点双。
为了方便,采用后者。
与强连通分量等不同,一个点可能属于多个点双,但是一条边属于恰好一个点双(如果定义采用前者则有可能不属于任何点双)。
那么在圆方树中,原来图中的点当做圆点,一个点双算作一个方点
而对于每一个点双连通分量,它对应的方点向这个点双连通分量中的每个点连边。
借用一下\(WC\)的图片。

这样建出来是一颗树或者森林。
那么这样建圆方树就是在\(tarjan\)跑点双的时候顺便连边了。

这样可以处理图上路径问题。

训练计划:
[SDOI2018]战略游戏
CF487E

原文地址:https://www.cnblogs.com/dixiao/p/14704106.html