记一场动态联通图专题

一场只有动态连通性的Gym

施工中…

A. Connect and Disconnect

加边,删边,询问图有多少个联通块

解题报告

首先将所有操作离线下来。显然一开始的答案为n
然后我们可以视消失的时间为权值,那么就是动态维护每个时刻的最大生成树。
对于加边操作:
1. 不连通,直接连通就好了。
2. 连通,找出这个联通块最小的边,然后比较权值,保留权值较大的那条边。答案不变
对于删边操作:
1. 不是树边就直接无视
2. 断开这条边,答案加一。因为当前边是已经加入的边里面删除时间最迟的,能够连接u,v的其他边要么已经被删除,要么还没被加入,所以可以放心地答案加一。

 


发表评论

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