日期: 2024 年 7 月 18 日

1 篇文章

P1197 [JSOI2008] 星球大战 题解
题目大意 有一个图,依次删去一些点后有多少个连通块。 思路 一道并查集 + 离线 的题目。 这道题第一眼肯定是想如何维护可以删除节点的并查集,但是这样不太可做。(或许是我太菜了。)但是我们发现他只有一个删除的操作,没有增加的操作,那么就可以想到离线计算。 离线计算,也就是把原本是读入后立马运算的操作都存起来,再算。 这样的好处就是我们可以按操作倒着…