根号分治
645 字
3 分钟
根号分治
上紫纪念,水一篇
昨晚 cf 的F:2285F - Mooclear Reactor 3
这是一个并查集,然后每次合并时如果爆炸就会全部拆成单点
就是是每次合并时检查是否爆炸,爆炸就拆开,不然就合并
拆开和合并均摊下来分别是 和 ,只有检查的复杂度比较高
对于检查是否爆炸:
-
考虑合并时暴力检查一个集合内所有点的邻接表,两个中心相连的菊花图,让中心之间的边在邻接表中靠后,反复合并中心点即可卡掉
-
考虑暴力检查合并的两个集合的所有点对,在两个集合都很大的时候显然也会爆
然后发现根号分治一下结合两个可以做,
也就是说
在待合并的两个集合都不是很大的时候一一检查,如果有一个很大就遍历总度数较少的集合检查是否在另一个集合
复杂度
Code( 用的题解的 ,马蜂交给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();}学习一下根号分治,核心是根据不同的数据规模选择不同的处理方式,使得每一类操作的总成本都可接受
小的情况直接暴力,大的情况则考虑数量少、出现次数少,或者专门预处理
先开个坑,
咕咕咕
文章分享
如果这篇文章对你有帮助,欢迎分享给更多人!
相关文章智能推荐
1
数论笔记
数学来点数论...
2
2026 CCPC 长春 游记
竞赛第一次ccpc qwq
3
第二十四届电子科技大学 ACM-ICPC 程序设计竞赛 初赛游记
竞赛第一次校赛qwq
4
Hexo 博客搭建教程
工程从零开始的个人博客搭建!
随机文章随机推荐
评论区
正在加载 Twikoo…
正在加载 Giscus…









