HDU 5458 Stability (双连通缩点,树链剖分)

一个图,可能存在自环或者重边,现在有两个操作:1. 将a-b这条边删除;2. 询问单独删除那些边可以使a和b不联通。

先对询问预处理,得出最终的图,然后将图双连通缩点,缩点完是一颗树,那么对树树链剖分下,然后逆着询问求解,对于询问2其实就是求a对应树的点和b对应树的点之间有多少条边。对于操作1如果a和b是在同一个连通分量就pass,否则就将a对应树的点到b对应树的点之间的边标记0,相当于不联通了,对树链的操作可以套一个线段树。

注意一点在标记删边时用set维护pair,map维护pair会跪。

 

LEAVE A COMMENT