题解 P1640 【[SCOI2010]连续攻击游戏】

· · 题解

并查集好啊

把每个装备的两个属性a,b看成边(a,b)，会形成一些连通块

如果连通块大小为k ，无环（树），答案是k−1，有环就是k

考虑如何合并两个连通块。

合并并查集x,y，若x\not =y，把数字小的父亲设为数字大的，给数字小的打上vis 标记。若x=y，给树根打上标记。

这样维护的并查集有很好的性质：要么所有vis=1 ，要么除根（最大点）外vis=1 。于是最后遍历一下输出答案就行了.

代码应该能自己写了