jzoj 3453_连通块_并查集

题目描述

你应该知道无向图的连通块的数量,你应该知道如何求连通块的数量。当你兴奋与你的成就时,破坏王Alice拆掉了图中的边。当她发现,每删去一条边,你都会记下边的编号,同时告诉她当前连通块的个数。

然而,对边编号简直就是个悲剧,因为Alice为了刁难你,拆掉编号从l到r的边,当然你需要做的事情就是求连通块的个数。如果你答对了,Alice会把拆掉的边装好,迚行下一次破坏。如果你无法完成这个任务,Alice会彻底毁了你的图。

进行完足够多次之后,Alice觉得无聊,就玩去了,而你却需要继续做第三题。


思路

两个并查集,f[i]表示前i条边所连成的点的集合,g[j]表示后j条边所连成的点的集合。 那么对于一个询问 [l,r],我们就可以通过合并f[l-1]和g[r+1]两个集合来确定有几个联通块


]]>