一个很奇妙的题。
回想起之前打的一场模拟赛，有一道题的部分问题是要维护动态图两两联通性的。可能不太一样，但是他有一个离线的思想，将没有修改过的边提前拎出来，把已知的联通性先求了，再用线段树分治一类的可撤销做法维护剩下边的修改。但是这样维护的复杂度跟修改次数相关非常大，如果修改次数一多起来，复杂度就会假。
但这道题给了我们一个解决方法：将操作分块。
将操作每 \(w\) 个分一块。那么涉及到的点最多 \(2w\) 个，边最多 \(w\) 条。剩下的边和点都可以缩起来。这一部分复杂度因为分了 \(\dfrac{q}{w}\) 块，复杂度是 \(\dfrac{q(n+m)}{w}\) 的，居然很对。对于 \(2w\) 个关键点，我们根据缩点后联通性建新图。每次查询时，暴力在新图中加入至多 \(k\) 条边后bfs，复杂度也是对的，非常奇妙。
块长可能因常数而异，需要自己去调，在 \(300\) 到 \(500\) 间都是合理的。
标签：2w,联通,修改,dfrac,复杂度,Dynamic,Gym103687K,Reachability From： https://www.cnblogs.com/hikkio/p/17591456.html