圆方树,是解决仙人掌问题的实用方法,假设最初图都是圆点,对于每个环新建一个方点并连接这个环上所有圆点,能很好规避同一个点可能属于很多个环的情况,并且发现build完之后是一棵树
广义圆方树,能够不局限于去解决仙人掌问题,能上升到无向图层面,很好解决图上路径类,等等问题
那么如何建立圆方树?有点类似 (v-dcc) ,建立方点,连接当前点双联通分量的所有点,实现通过tarjan算法
但注意 (v-dcc) 把整个点双联通分量都缩成一个点了,圆方树还保持着圆点,也就是说圆方树点数是 (n+k) ,其中 (k) 标号是点双个数
具体实现不详讲,但存在值得注意的细节:
令 (now) 为当前 (dfs) 到的节点, (y) 为其搜索树上的一个儿子。注意, (now) 与 (y) 在栈中不一定相邻。也就是说,下面两种写法:
- 弹出栈顶直到弹出 (now) 为止;最后再压入 (now)
- 弹出栈顶直到弹出 (y) 为止,最后再将虚点向 (now) 连边
前者错误,后者正确。
代码:
void tarjan(int x){
++nown;
dfn[x]=low[x]=++num;
st.push(x),w[x]=-1;
for(int i=head[x];i;i=edge[i].Next){
int to=edge[i].to;
if(!dfn[to]){
tarjan(to);
low[x]=min(low[x],low[to]);
if(low[to]>=dfn[x]){
addedge2(++diannum,x),addedge2(x,diannum);
++w[diannum];
while(1){
addedge2(diannum,st.top()),addedge2(st.top(),dia服务器托管网nnum);
++w[diannum];
if(st.top()==to){
st.pop();
break;
}
st.pop();
}
}
}
else low[x]=min(low[x],dfn[to]);
}
}
(v-dcc) 和圆方树运用区别何在?后者对于点双内部的处理能够非常方便,而前者似乎处理整个点双对答案的贡献(不考虑单点)会十分好搞
圆方树的性质:
-
是树
-
每条边都是方点和圆点服务器托管网连接边
-
每个方点对应一个点双联通分量
-
方点的度数是点双联通分量的大小
-
圆点是割点才有超过1个儿子,否则只连接一个方点儿子
-
圆方树上两个点的路径经过的圆点是图上两点之间的必经点
还有一些点双的小性质:对于一个点双的两点,它们之间简单路径的并集等于这个点双集合
圆方树能够很好地将无向图上问题转化为树上问题,进行统计类的时候可能割点会被统计多次,所有一般把方点赋为-1,然后就很好做了,等等就不细说了
服务器托管,北京服务器托管,服务器租用 http://www.fwqtg.net
机房租用,北京机房租用,IDC机房托管, http://www.fwqtg.net