根号分治

645 字
3 分钟
根号分治
根号分治

上紫纪念,水一篇

Codeforces
Codeforces

昨晚 cf 的F:2285F - Mooclear Reactor 3

这是一个并查集,然后每次合并时如果爆炸就会全部拆成单点

就是是每次合并时检查是否爆炸,爆炸就拆开,不然就合并

拆开和合并均摊下来分别是 O(q)O(q) 和 O((n+q)log⁡n)O((n+q)\log n) ,只有检查的复杂度比较高

对于检查是否爆炸:

  • 考虑合并时暴力检查一个集合内所有点的邻接表,两个中心相连的菊花图,让中心之间的边在邻接表中靠后,反复合并中心点即可卡掉

  • 考虑暴力检查合并的两个集合的所有点对,在两个集合都很大的时候显然也会爆

然后发现根号分治一下结合两个可以做,

也就是说

在待合并的两个集合都不是很大的时候一一检查,如果有一个很大就遍历总度数较少的集合检查是否在另一个集合

复杂度 O(qBlog⁡m+qmB)O(qB\log m+\dfrac{qm}{B})

Code( BB 用的题解的 m5\dfrac{\sqrt{m}}{5} ,马蜂交给ai优化了一下)

#include <bits/stdc++.h>
using namespace std;
void solve() {
int n, m, q;
cin >> n >> m >> q;
vector<vector<int>> g(n + 1);
for (int i = 0; i < m; ++i) {
int x, y;
cin >> x >> y;
g[x].push_back(y);
g[y].push_back(x);
}
for (int i = 1; i <= n; ++i)
sort(g[i].begin(), g[i].end());
vector<int> bel(n + 1), degree_sum(n + 1);
vector<vector<int>> members(n + 1);
auto reset = [&](int x) {
bel[x] = x;
members[x] = {x};
degree_sum[x] = g[x].size();
};
for (int i = 1; i <= n; ++i)
reset(i);
int B = max(1, int(sqrt(m) / 5));
int ans = n;
auto conflict = [&](int u, int v) -> bool {
if (!degree_sum[u] || !degree_sum[v])
return false;
if (members[u].size() <= B && members[v].size() <= B) {
for (int x : members[u]) {
if (g[x].empty()) continue;
for (int y : members[v])
if (binary_search(g[x].begin(), g[x].end(), y))
return true;
}
} else {
if (degree_sum[u] > degree_sum[v])
swap(u, v);
for (int x : members[u])
for (int y : g[x])
if (bel[y] == v)
return true;
}
return false;
};
while (q--) {
int x, y;
cin >> x >> y;
int u = bel[x], v = bel[y];
if (u != v) {
if (conflict(u, v)) {
vector<int> atoms = members[u];
atoms.insert(atoms.end(),
members[v].begin(), members[v].end());
ans += int(atoms.size()) - 2;
for (int z : atoms)
reset(z);
} else {
if (members[u].size() < members[v].size())
swap(u, v);
for (int z : members[v]) {
bel[z] = u;
members[u].push_back(z);
}
members[v].clear();
degree_sum[u] += degree_sum[v];
degree_sum[v] = 0;
--ans;
}
}
cout << ans << '\n';
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t;
cin >> t;
while (t--)
solve();
}

官方题解


学习一下根号分治,核心是根据不同的数据规模选择不同的处理方式,使得每一类操作的总成本都可接受

小的情况直接暴力,大的情况则考虑数量少、出现次数少,或者专门预处理

先开个坑,

咕咕咕

文章分享

如果这篇文章对你有帮助,欢迎分享给更多人!

根号分治
https://azusaaa.com/posts/sqrt-decomposition/
作者
dsyfb_437
发布于
2026-11-16
许可协议
CC BY-NC-SA 4.0

评论区

正在加载 Twikoo…
Profile Image of the Author
dsyfb_437
My love shines, dims, and flickers. Am I a star, then?
公告
欸,你是怎么发现这个的...
分类
标签
最新动态
站点统计
文章
5
分类
4
标签
8
总字数
5,714
运行时长
0 天
最后活动
0 天前
站点信息
构建平台
Local
博客版本
Firefly v6.16.8
文章许可
CC BY-NC-SA 4.0

当前页面没有目录

文章目录

当前页面没有目录