P1197 [JSOI2008]星球大战-逆序并查集与连通块

题目链接[JSOI2008]星球大战 - 洛谷
连通块个数很显然是集合个数，这题常规做法肯定是按照顺序连边，然后跑一边计算集合个数，很显然会超时，考虑逆序处理，即，把能摧毁的全部摧毁，统计连通块个数，代表最后一次操作后连通块个数，然后从最后一个开始补点，遍历其能连接的点，如果不在一个集合而且没被摧毁，那么连通块个数就要减1，即发现了应该联通但分属于两个集合的子集。
# include
# include

using namespace std;

bool broken[200000+10];
typedef struct
{
int b,e;

}xinxi;
int fa[100000+10];
xinxi s[200000*2+10];
int f[200000*2+10];
int nex[200000*2+10];
int getf(int x)
{

P1197 [JSOI2008]星球大战-逆序并查集与连通块最先出现在Python成神之路。