cdq分治+可撤销并查集

1.bzoj 3237 [Ahoi2013]连通图

题意:给一个连通的无向图,无重边无自环,k个询问,每次询问给出不超过4条原图中的边,问将这些边删掉后,无向图是否还是保持连通。一个图是连通的当且仅当任意两个不同的点之间存在一条路径连接他们。

做法:cdq分治+可撤销并查集。每次先加入在右半区间且不在左半区间的边,递归到左半边,撤销,再加入在左半区间且不在右半区间的边,递归到右半边,撤销。

 

未完待续…