[ONTAK2015] Bajtocja 题解.pdf
需积分: 0 62 浏览量
2023-01-16
10:35:17
上传
评论
收藏 141KB PDF 举报
[ONTAK2015] Bajtocja 题解
题目大意
有 个初始为空的有 个点的图，有 个操作，每个操作在其中一个图上面连一条边。对于每次
操作，询问操作后有多少个点对 满足在每个图里面都是联通的。
算法
有《不可以，总司令》的经验，我们考虑用哈希。
对于图的连通性，发现如果两个点联通，那么它们在一个并查集内。所以哈希状压每个点所在连通
块。具体地，设 为点 在图 所在的并查集的根， 为点 在第 个图的哈希值，那么设
表示 所在连通块的状压。那么维护点对 的数量就是维护点对 的数量，用桶维护。
合并并查集可以用启发式合并，枚举小并查集内的每一个点，更新其 和 . 这样均摊是
的。
但是直接用 map 或 unordered_map 维护桶会 TLE ，手写普通的哈希也过不了，所以引入
链式哈
希
这种科技。( 似乎叫它链式前向哈希更贴切。)
其实就是对于哈希冲突，建立链式前向星，每个哈希值对应多个键值。
其实不释放哈希空间可以过，但是我这里还是写一下。对于桶的一个位置为 ，我们把这个哈希值
从链式前向星中删除掉会优化。具体实现方式如下：
这样就能 AC 了。
void del(ull x)
{
int y = x%H;
if (to[last[y]] == x)
{
last[y] = nx[last[y]];
return;
}
for (int i = nx[last[y]], ls = last[y]; i; ls = i, i = nx[i]) if (to[i]
== x)
{
nx[ls] = nx[i];
return;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
资源评论
