LuoguP1197(并查集)

题目大意

给定$n$个点$m$条边的无向图,每次删除一个点,询问联通块的个数。

分析

我们观察询问的为联通块个数,很容易想到并查集。但这道题麻烦的地方就是并查集并不支持删除操作。

重新思考并查集支持的操作,我们发现并查集虽然不支持删除点操作,但可以插入点来维护联通块个数。

于是,可以用离线的操作,先将所有题目要求删除的点删去,计算答案,接下来一个个加点,计算新的联通块个数。

这道题的思路难点就在于要将删除点操作更改为插入点操作,想清楚这一点这道题就好做了。

代码

为了保证网站的安全,特将代码从solution中将code分离。
Code : 戳我!!!!! (速度较慢,请耐心等待)