[图论][双联通分量][无向图仙人掌] UVALive 3514 Cactus

题意:求出给定图的生成子图里有多少个是仙人掌。

首先明确生成子图的概念:包括所有的顶点的子图(之前没有弄明白这个一直没有想出来),那么这个操作其实就很简单了,首先判断图形是否为仙人掌,如果是的话把其中所有的圈(其实在这里就是点双联通分量)所包含的的数量算出来,Π(cnt[i]+1)即为结果(每个圈最多只能去掉一个边)。

首先,判断是否为仙人掌,这个可以利用无向图仙人掌的性质在dfs求双联通分量的时候顺便求出来:对于任意一个dfs树上的节点u,他的反向边数量+他的子节点中low值小于pre[u]的数量<2,如果大于等于2说明这个节点附近已经产生了两个环了,不可能是仙人掌,反之如果所有点都满足这个要求,那么一定是仙人掌。

其次,求每一个圈的边数。这里如果是仙人掌的话,一定每个点双联通分量都是一个圈(否则就会被判定为非仙人掌,所以这里首先保证第一步的正确性是很重要的),这样的话只需要在求点双联通分量时在退栈的时候把每个bcc对应的边的数量记录下来就可以了(注意是边的数量而不是点的)。

最后套一个无聊的高精度板子就ok了,因为格式错误wa了几次。。。UVALive貌似经常有把格式错误当成wa的。。。顺便这个对高精度的要求还挺高,1000位都满足不了开了100000位才过,至于吗呵呵

继续阅读“[图论][双联通分量][无向图仙人掌] UVALive 3514 Cactus”