首页 > 代码库 > [codevs 1995]黑魔法师之门(并查集)

[codevs 1995]黑魔法师之门(并查集)

题目:http://codevs.cn/problem/1995/

分析:脑补一下满足题目要求的子图肯定就是环……于是题目就变成了不断加边求环的个数。看起来有点麻烦……但是环的实质是几个小环组合起来的……所以我们只需要知道最基础的环的个数就行了,根据二项式定理那么就是2^(最基础的环的个数)-1。还是不好做啊!!!!!!

没关系……并查集来了……

假设对于第i-1操作后,最终答案为ans,那么对于第i次操作,分为两种情况

  ①加入这条边后,没有出现新环,那么说明对结果无影响,结果还是ans

  ②加入这条边后,出现了新环。那么对于以前的ans种环,我们可以帮这个新环放进去组合作为新的环,于是ans*2,但是要注意我们还多了一个新的基础的环,所以ans=ans*2+1

于是完美解决……

[codevs 1995]黑魔法师之门(并查集)