CF292D Connected Components 题解
2022/4/14 23:16:18
本文主要是介绍CF292D Connected Components 题解,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
这道题给各位一种与之前不一样的做法。
首先显然可以使用并查集维护连通块个数,但是我们知道并查集 不支持删除,而题目是 区间询问,所以:
不支持删除+区间询问=回滚莫队!
所以这道题可以用回滚莫队通过,没学过的可以看看 这篇博文。
那么对于这题,取块长 \(block = n^{\frac{2}{3}}\),对所有询问进行离线排序之后我们按照回滚莫队的一般套路来处理。
但是:这道题又不是正宗的回滚莫队,因为并查集不支持删除,所以我们需要作一点变通:我们让右指针 \(r\) 往回移而不是从块的右边往右移,而且如果一个询问在块内,我们不需要单独暴力处理,直接一起处理。
而且在块与块的转移之间,假设当前刚刚做完第 \(i\) 块,那么我们就需要将 \([1,(i - 1) * block + 1]\) 里面的所有连边操作完成。因为 \(n\) 只有 500,所以不会 TLE。
时间复杂度为 \(O(m^{\frac{5}{3}}n)\),但常数稍微有一点大。
代码:
#include <bits/stdc++.h> using namespace std; typedef long long LL; const int MAXN = 500 + 10, MAXM = 1e4 + 10, MAXK = 2e4 + 10; int n, m, k, ans[MAXK], fa2[MAXN], fa3[MAXN], total, ys[MAXM], block, x[MAXM], y[MAXM], bnum; struct node { int l, r, id; }q[MAXK]; int read() { int sum = 0, fh = 1; char ch = getchar(); while (ch < '0' || ch > '9') {if (ch == '-') fh = -1; ch = getchar();} while (ch >= '0' && ch <= '9') {sum = (sum << 3) + (sum << 1) + (ch ^ 48); ch = getchar();} return sum * fh; } bool cmp(const node &fir, const node &sec) { if (ys[fir.l] ^ ys[sec.l]) return ys[fir.l] < ys[sec.l]; return fir.r > sec.r; } int gffa3(int x) {return (fa3[x] == x) ? x : fa3[x] = gffa3(fa3[x]);} void hbfa3(int r) {if (gffa3(x[r]) != gffa3(y[r])) fa3[fa3[x[r]]] = fa3[y[r]];} int main() { n = read(), m = read(); block = ceil(pow(m, 2.0 / 3.0)); bnum = ceil((double)m / block); for (int i = 1; i <= m; ++i) x[i] = read(), y[i] = read(); for (int i = 1; i <= m; ++i) ys[i] = (i - 1) / block + 1; k = read(); for (int i = 1; i <= k; ++i) q[i].l = read(), q[i].r = read(), q[i].id = i; for (int zzh = 1; zzh <= n; ++zzh) fa3[zzh] = zzh; sort(q + 1, q + k + 1, cmp); int j = 1; for (int i = 1; i <= bnum; ++i) { int l = (i - 1) * block + 1, r = m; while (j <= k) { if (ys[q[j].l] > i) break; while (r > q[j].r) { hbfa3(r--); } for (int zzh = 1; zzh <= n; ++zzh) fa2[zzh] = fa3[zzh];//复制一份 while (l < q[j].l) { hbfa3(l++); } int total = 0; for (int zzh = 1; zzh <= n; ++zzh) if (gffa3(zzh) == zzh) total++; ans[q[j].id] += total; l = (i - 1) * block + 1; for (int zzh = 1; zzh <= n; ++zzh) fa3[zzh] = fa2[zzh];//回复数组 j++; } for (int zzh = 1; zzh <= n; ++zzh) fa3[zzh] = zzh; for (int zzh = 1; zzh <= min(m, i * block); ++zzh) hbfa3(zzh); } for (int i = 1; i <= k; ++i) printf("%d\n", ans[i]); return 0; }
这篇关于CF292D Connected Components 题解的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-15PingCAP 黄东旭参与 CCF 秀湖会议,共探开源教育未来
- 2024-05-13PingCAP 戴涛:构建面向未来的金融核心系统
- 2024-05-09flutter3.x_macos桌面os实战
- 2024-05-09Rust中的并发性:Sync 和 Send Traits
- 2024-05-08使用Ollama和OpenWebUI在CPU上玩转Meta Llama3-8B
- 2024-05-08完工标准(DoD)与验收条件(AC)究竟有什么不同?
- 2024-05-084万 star 的 NocoDB 在 sealos 上一键起,轻松把数据库编程智能表格
- 2024-05-08Mac 版Stable Diffusion WebUI的安装
- 2024-05-08解锁CodeGeeX智能问答中3项独有的隐藏技能
- 2024-05-08RAG算法优化+新增代码仓库支持,CodeGeeX的@repo功能效果提升