[BZOJ1015][JSOI2008]星球大战starwar

题目大意

BZOJ1015
告诉你一张图,以边的形式给出。在给出k个操作,每次操作删除一个点和它的边。查询每次操作后的联通块的数目。

 

做法

倒着向图里添加点,及时维护联通块的数目。维护联通块数目运用并查集。如果添加的边两点不在同一个集合,那么联通块数目减一,并集。如果在,那则不用处理。

 

代码

代码还算简单。但我写的比较丑。

 

One thought on “[BZOJ1015][JSOI2008]星球大战starwar

  1. Pingback: 并查集 介绍 | 火药

发表评论

电子邮件地址不会被公开。 必填项已用*标注