题解 P5214 【[SHOI2014]神奇化合物】
pigstd
·
·
题解
我们先考虑暴力
很容易想到一个O((m+n) \times q)的算法:用链表存图,用二维数组记录删去的边,然后每次查询就暴力dfs
然后我们可以发现,虽然m很大,但是q很小,这意味着大多数边是永远不会被删除的,所以我们可以离线,先用并查集把所有永远不会被删掉的边缩成一个点,然后暴力就好了
设查询的次数为k,时间复杂度大概是O(((q-k)+n) \times k),能跑过去
code:正解
总结:在遇到不会做的题目时候,可以观察数据范围的特殊性,然后暴力对症下药