题解 P5214 【[SHOI2014]神奇化合物】

· · 题解

我们先考虑暴力

很容易想到一个O((m+n) \times q)的算法：用链表存图，用二维数组记录删去的边，然后每次查询就暴力dfs

然后我们可以发现，虽然m很大，但是q很小，这意味着大多数边是永远不会被删除的，所以我们可以离线，先用并查集把所有永远不会被删掉的边缩成一个点，然后暴力就好了

设查询的次数为k，时间复杂度大概是O(((q-k)+n) \times k)，能跑过去

code：正解

总结：在遇到不会做的题目时候，可以观察数据范围的特殊性，然后暴力对症下药