题解 P3820 【小D的地下温泉】

· · 题解

对于30%的数据

对于每个点的询问，我们可以直接暴力BFS，直接比较即可。

对于70%的数据

直接将图存在一个1000\times 1000的数组里。然后将每个联通块的块的大小存在一个点上。如果将温泉变为土，由于不会将一个块分割，所以直接v[fa(x)]--即可；如果将土变为温泉，那么为这块地新开一个位置，然后将这个点四周的大小合并到这个点上即可。以上均可以用并查集来维护。

对于100%的数据

只需在70分的基础上加一些小技巧将图存在一个10^{6}的数组里即可。

另外，不推荐使用在原位置直接重开点的方法维护大小，可能会导致一些本不联通的联通块的数据联通的情况。

以上为被dalaoD翻的水题题解

最后感谢Ditoly和FallDream帮助验题。