【题解】洛谷P1197 [JSOI2008]星球大战

题目

洛谷P1197[JSOI2008]星球大战

题解

判断两个星球的连通性以及计算连通块的个数,可以使用并查集。但是,并查集不容易实现删除操作,所以要从问题的反面考虑,即从最终的局面开始,逐个添加被消灭的星球。实时计算连通块的数量,若两个连通块合并,则数量减一。

一些与题目本身无关的提醒:定义vector<int> v后,如果容器是空的,不能用v[]=直接赋值,如果容器内有超过i个元素(即v[i]存在),才可以直接访问v[i]。 变量名不要用kill(与库函数重名?)。

代码

Subscribe
提醒
guest
0 评论
Inline Feedbacks
View all comments