圆方树 useful things

发布时间 2023-11-09 09:43:42作者: blueparrot

圆方树,是解决仙人掌问题的实用方法,假设最初图都是圆点,对于每个环新建一个方点并连接这个环上所有圆点,能很好规避同一个点可能属于很多个环的情况,并且发现build完之后是一棵树

广义圆方树,能够不局限于去解决仙人掌问题,能上升到无向图层面,很好解决图上路径类,等等问题

那么如何建立圆方树?有点类似 \(v-dcc\) ,建立方点,连接当前点双联通分量的所有点,实现通过tarjan算法

但注意 \(v-dcc\) 把整个点双联通分量都缩成一个点了,圆方树还保持着圆点,也就是说圆方树点数是 \(n+k\) ,其中 \(k\) 标号是点双个数

具体实现不详讲,但存在值得注意的细节:

\(now\) 为当前 \(dfs\) 到的节点, \(y\) 为其搜索树上的一个儿子。注意, \(now\)\(y\) 在栈中不一定相邻。也就是说,下面两种写法:

  1. 弹出栈顶直到弹出 \(now\) 为止;最后再压入 \(now\)
  2. 弹出栈顶直到弹出 \(y\) 为止,最后再将虚点向 \(now\) 连边
    前者错误,后者正确。

\(v-dcc\) 和圆方树运用区别何在?后者对于点双内部的处理能够非常方便,而前者似乎处理整个点双对答案的贡献(不考虑单点)会十分好

圆方树的性质:

  1. 是树
  2. 每条边都是方点和圆点连接边

(咕咕咕)