并查集

1. 并查集

每次合并两个不相交集合，或者询问两个元素是否在同一个集合里。

洛谷 P1197 [JSOI2008] 星球大战

给一张图，每次删掉一个点及相连的边，求剩下的图中的联通块数。

我们倒着从空图往回做，就变成了加边求联通块数的问题。

洛谷 P1525 [NOIP2010 提高组] 关押罪犯

有一张图，边有边权。你要给每个点确定是黑色或者白色，使得两端颜色相同的边的边权最大值最小。

solution 1

一个直观想法是尽可能让边权大的边，两端颜色不同。因此我们从大到小加边，由于不能确定两端点是什么颜色，考虑用并查集维护一个相对关系，就是敌人的敌人是朋友这种感觉，如果一条边两端点在同一集合，直接输出即可。

solution 2

考虑二分，假设二分到一个 \(\texttt{mid}\)，如果大于 \(\texttt{mid}\) 的边构成一个二分图就是可行的。

带权并查集

维护当前节点 \(x\) 与其父亲的关系。

P2024 [NOI2001] 食物链

有三种生物 \(A,B,C\)，其中 \(A\) 吃 \(B\)，\(B\) 吃 \(C\)，\(C\) 吃 \(A\)。
有 \(n\) 个生物，每个要么是 \(A\)，要么 \(B\)，要么 \(C\)。
每次告诉你谁吃谁或者谁和谁同类，或者问你谁吃谁/谁和谁同类是否一定不成立。

使用带权并查集，维护节点 \(x\) 与其父亲 \(fa\) 的关系，记为 \(d_x\)：

• 如果 \(d_x=0\)，那么 \(x\) 与其父亲 \(fa\) 是同类。
• 如果 \(d_x=1\)，那么 \(x\) 吃 \(fa\)。
• 如果 \(d_x=2\)，那么 \(x\) 被 \(fa\) 吃。

一些神奇的性质就是：

• \(A \stackrel{s_1}{\longrightarrow} B \stackrel{s_2}{\longrightarrow} C \Rightarrow A \stackrel{s_1+s_2}{\longrightarrow} C\)
• \(A \stackrel{s_1}{\longrightarrow} B \Rightarrow B \stackrel{-s_1}{\longrightarrow} A\)

（以上运算都是在模 \(3\) 意义下进行的）

之后再合并/路径压缩的时候用上述性质讨论一下就可以了，不再赘述。

P8779 [蓝桥杯 2022 省 A] 推导部分和

有一列数字，每次告诉你一个区间的和，或者问能否确定一个区间的和。

考虑两两元素之间的缝隙，共有 \(n+1\) 个缝隙（加上第一个元素之前的和第 \(n\) 个元素之后的）。依次编号，告诉你一个区间的和本质上就是在讲从一个缝隙走到另一个缝隙的距离。例如 \(l \sim r\) 的和是 \(s\) 就是第 \(l\) 个缝隙到 \(r+1\) 个缝隙的距离是 \(s\)。考虑带权并查集，与上一题的做法基本类似。

将某些区间问题视作关于缝隙的图是一类特殊技巧，有必要掌握一下。