并查集-下
基本介绍
并查集的小扩展（下节课的题目重点展示）：可以定制信息：并查集目前有多少个集合，以及给每个集合打上标签信息
带权并查集、可持久化并查集、可撤销并查集，都是备战算法竞赛的同学必学的内容，这些内容会在【挺难】阶段的课程里安排讲述
移除最多的同行或同列石头
题目链接
https://leetcode.cn/problems/most-stones-removed-with-same-row-or-column/
思路分析
⭐ 结论：同行或者同列的元素合并在一起，从边缘开始往中间消，一定会剩下一个石头
将同行或者同列的元素加入一个集合中，然后每个并查集最终会剩余一块石头，需要消除的石头数量为总的石头数量减去集合的个数
本题中石头的坐标很大，但是石头的个数不多，可以用两个 hash 表处理，key 为石头的坐标，value 为石头编号，一个为行表，记录 x 坐标处是否有石头，一个为列表，记录 y 坐标处是否有石头，后续判断是否同行或者同列只需要查表中的 key 是否存在，若存在，则说明同行或者同列
代码实现
java
class Solution {
// key : 某行，value : 第一次遇到的石头编号
HashMap<Integer, Integer> rowFirst = new HashMap<>();
HashMap<Integer, Integer> colFirst = new HashMap<>();
int MAXN = 1001;
int[] father = new int[MAXN];
int sets;
public int removeStones(int[][] stones) {
int n = stones.length;
build(n);
for (int i = 0; i < n; i++) {
int row = stones[i][0];
int col = stones[i][1];
// 将同行或者同列石头的编号 union
// 如果之间没有就放入，否则 union
if (!rowFirst.containsKey(row)) {
rowFirst.put(row, i);
} else {
union(i, rowFirst.get(row));
}
if (!colFirst.containsKey(col)) {
colFirst.put(col, i);
} else {
union(i, colFirst.get(col));
}
}
// 将同行或者同列的石头放入一个集合中
// 每个集合中消除后最后一定会剩余一快石头
// 消除石头的个数 = 总的石头数量 - 集合的个数
return n - sets;
}
public void build(int n) {
for (int i = 0; i < n; i++) {
father[i] = i;
}
sets = n;
}
public int find(int n) {
if (n == father[n]) {
return n;
}
return father[n] = find(father[n]);
}
public void union(int x, int y) {
int fx = find(x);
int fy = find(y);
if (fx == fy) {
return;
}
father[fx] = fy;
// 合并和之后集合个数需要减少
sets--;
}
}找出知晓秘密的所有专家
题目链接
https://leetcode.cn/problems/find-all-people-with-secret/
思路分析
本题采用给集合打标签的技巧，类似于并查集基础模板代码中的 size 数组，size [ i ] 表示 i 位置的元素所在集合的大小
本题简历 secret 数组，以该集合的根节点为代表，打标签，表示该集合的人是否知道秘密
根据题意，同一时间开会的人会传播秘密，按开会时间分组处理，所以首先需要将数组按照开会时间从小到大排序
接下来处理不同的组，同一时刻开会的人都放在一个集合中，如果集合中的某个人知道秘密，则该集合的人都会知道秘密，给该集合打上标签
如果该集合中无人知道秘密，会议结束，需要做小的撤销操作，将集合中的每个人还原为 build 的状态，即每个人单独一个集合
时间复杂度：O（m * log m） + O（m） + O（n），m 表示有几场会议
代码实现
java
class Solution {
int MAXN = 100001;
int[] father = new int[MAXN];
// 打标签，secret[代表元素] 表示该集合的人是否知道秘密
boolean[] secret = new boolean[MAXN];
public List<Integer> findAllPeople(int n, int[][] meetings, int firstPerson) {
build(n, firstPerson);
// 按照开会时间排序
Arrays.sort(meetings, (a, b) -> a[2] - b[2]);
int m = meetings.length;
for (int l = 0, r; l < m;) {
// 首先进行分组，[l,r] 的元素都是在同一时间开会的
r = l;
while (r + 1 < m && meetings[l][2] == meetings[r + 1][2]) {
r++;
}
// 同一时间开会的加入一个集合中
for (int i = l; i <= r; i++) {
union(meetings[i][0], meetings[i][1]);
}
// 小的撤销行为，如果集合中无人知晓秘密，拆散集合
// 即将元素从集合中移除，回到 build 的状态，父节点为自己
for (int i = l, a, b; i <= r; i++) {
a = meetings[i][0];
b = meetings[i][1];
if (!secret[find(a)]) {
father[a] = a;
}
if (!secret[find(b)]) {
father[b] = b;
}
}
// 来到下一组
l = r + 1;
}
// 遍历每个专家，收集知晓秘密的专家，返回
List<Integer> ans = new ArrayList<>();
for (int i = 0; i < n; i++) {
if (secret[find(i)]) {
ans.add(i);
}
}
return ans;
}
public void build(int n, int first) {
for (int i = 0; i < n; i++) {
father[i] = i;
// 初始时都不知道秘密
secret[i] = false;
}
// 初始时，专家 0 把秘密告诉给了 firstPerson
father[first] = 0;
// 以集合的根节点为代表，打标签，表示该集合的人是否知道秘密
secret[0] = true;
}
public int find(int n) {
if (n == father[n]) {
return n;
}
return father[n] = find(father[n]);
}
public void union(int x, int y) {
int fx = find(x);
int fy = find(y);
if (fx == fy) {
return;
}
father[fx] = fy;
// 链接之后，查看该集合的根节点是否知道秘密
// 是否知道秘密取决于该集合是否需要被拆散
// 这里的 | 运算解释如下
// （1）如果 y 集合知晓秘密，| 运算之后整个集合仍然知晓秘密
// （2）如果 y 集合不知晓秘密，但是 x 集合知晓秘密，| 运算之后
// 合并后的整个大集合中的人都知晓秘密
secret[fy] |= secret[fx];
}
}好路径的数目（难）
题目链接
https://leetcode.cn/problems/number-of-good-paths/
思路分析
按照边中两个顶点的最大值从小到大排序，边中两个顶点最大值较小的边先处理
好路径的定义：（1）本节点到本节点的边，因为符合边的两个节点值相同（2）边的两个节点的值相同，且中间节点的值小于等于两个节点的值
打标签：每个集合记录（1）最大值（2）最大值的个数
遍历每一条边，判断两个节点是否相同，如果相同，则好路径的条数为两个节点所在集合的最大值个数相乘，如果不存在，什么也不做，最后都要将两个节点所在的集合合并
每个集合中以节点值较大的节点做代表节点，这样做的目的是好处理，如果是集合合并，则以两个集合中最大节点值较大的那个集合为基准，将最大节点值较小的集合合并到最大节点值较大的集合中
代码实现
java
class Solution {
int MAXN = 30001;
// 需要保证集合中，代表节点的值，一定是整个集合的最大值
int[] father = new int[MAXN];
// 集合中最大值的个数，也就是集合中代表节点的值有几个
int[] maxcnt = new int[MAXN];
public int numberOfGoodPaths(int[] vals, int[][] edges) {
int n = vals.length;
build(n);
int ans = n;
// 按照边中两个顶点的最大值从小到大排序
Arrays.sort(edges, (e1, e2) -> (Math.max(vals[e1[0]], vals[e1[1]]) - Math.max(vals[e2[0]], vals[e2[1]])));
for (int[] edge : edges) {
ans += union(edge[0], edge[1], vals);
}
return ans;
}
public void build(int n) {
for (int i = 0; i < n; i++) {
father[i] = i;
// 初始时自己为一个集合，代表节点为自己
// 集合中的最大值个数为 maxcnt[代表节点]
maxcnt[i] = 1;
}
}
public int find(int n) {
if (n == father[n]) {
return n;
}
return father[n] = find(father[n]);
}
public int union(int x, int y, int[] vals) {
// fx 表示 x 所在集合的代表节点，同时也是 x 所在集合最大值的下标
int fx = find(x);
// fy 表示 y 所在集合的代表节点，同时也是 y 所在集合最大值的下标
int fy = find(y);
int path = 0;
// 边的两个节点值相同的才是好边
// 不是好边，什么也不做，合并
if (vals[fx] > vals[fy]) {
// 遵循小挂大原则
father[fy] = fx;
} else if (vals[fx] < vals[fy]) {
father[fx] = fy;
} else if (vals[fx] == vals[fy]) {
// 是好边，计算 path，合并
path = maxcnt[fx] * maxcnt[fy];
// 由于相等，谁挂谁都无所谓
father[fy] = fx;
// 集合合并，更新最大值的个数
maxcnt[fx] += maxcnt[fy];
}
return path;
}
}尽量减少恶意软件的传播
题目链接
https://leetcode.cn/problems/minimize-malware-spread-ii/
思路分析
题目中指明 graph [ i ] [ j ] == graph [ j ] [ i ]，则一定是无向图
将图中的节点分为两类，普通点，源头点（病毒点），普通点合并到一个集合中，如果一个集合被两个病毒点关联，则认为这个集合是无效的，因为移除一个病毒点之后还是会被感染
本题就是问移除感染源头点后，能拯救节点的最大个数，返回多个感染源头点中较小的编号
代码实现
java
class Solution {
// 如果测试数据变大，就改变这个值
int MAXN = 301;
// 存储每个点是不是病毒
boolean[] virus = new boolean[MAXN];
// 删掉源头点之后，能拯救多少个节点
int[] cnts = new int[MAXN];
// 集合的标签 : 感染整个集合的点是什么点
// a 是集合的代表点，整个集合的感染源头点是 infect[a]
// infect[a] == -1，目前这个集合没有发现感染源头点
// infect[a] >= 0，目前这个集合感染源头点是 infect[a]
// infect[a] == -2，目前这个集合感染源头点不止一个，无法拯救
int[] infect = new int[MAXN];
int[] father = new int[MAXN];
// 集合的标签 : 集合的大小是多少，并没有小挂大的含义
int[] size = new int[MAXN];
// 集合一定只放普通点，源头点根本不参与集合，也不是元素！
public int minMalwareSpread(int[][] graph, int[] initial) {
int n = graph.length;
build(n, initial);
// 不是病毒的点合并到一个集合中
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (graph[i][j] == 1 && !virus[i] && !virus[j]) {
union(i, j);
}
}
}
// 设置每个集合的感染源头点
for (int sick : initial) {
// 0 1 2 3
// 1
// 2 -> 病毒点
// 3
// 以上是节点的编号，题意是无向图，通过邻接矩阵表示是否相连
// 遍历节点，判断是否与病毒点相连
for (int neighbor = 0; neighbor < n; neighbor++) {
// 邻居不能是自己，同时也不能是病毒，并且邻居与病毒点相连
if (sick != neighbor && !virus[neighbor] && graph[sick][neighbor] == 1) {
// 找到邻居所在集合的代表点
int fn = find(neighbor);
// 给集合设置感染源头点
if (infect[fn] == -1) {
infect[fn] = sick;
} else if (infect[fn] != -2 && infect[fn] != sick) {
// 不等于 -1，则可能 > 0 或者 = -2
// 即说明（1）该集合已经有感染源头点了（2）已经无效了
// infect[fn] != -2 表示之前已经有感染源头点了，现在
// 又遇到一个感染源头点，该集合无法拯救，设置为 -2
// 1. 如果已经无效了，维持无效即可
// 2. 如果之前有感染源头点了( > 0 )，分两种情况讨论
// （1）源头点 = x：发现新的源头点是之前的源头点，维持 x
// （2）源头点 != x：集合中的一个元素已经连接了源头点，又发现
// 集合中的另一个元素连接了源头点 x，此时这个集合是拯救的
infect[fn] = -2;
}
}
}
}
// 统计拯救节点
for (int i = 0; i < n; i++) {
// 只关注集合的代表点，并且该集合有感染源头点
if (i == find(i) && infect[i] >= 0) {
// cnts 数组表示删掉源头点之后，能拯救多少个节点
// 该感染源头点的贡献需要类加上该集合的大小
cnts[infect[i]] += size[i];
}
}
// 对所有感染源头点的编号排序，返回较小的那个
Arrays.sort(initial);
int ans = initial[0];
int max = cnts[ans];
for (int i : initial) {
if (cnts[i] > max) {
ans = i;
max = cnts[i];
}
}
return ans;
}
public void build(int n, int[] initial) {
for (int i = 0; i < n; i++) {
father[i] = i;
size[i] = 1;
virus[i] = false;
cnts[i] = 0;
infect[i] = -1;
}
for (int i : initial) {
virus[i] = true;
}
}
public int find(int n) {
if (n == father[n]) {
return n;
}
return father[n] = find(father[n]);
}
public void union(int x, int y) {
int fx = find(x);
int fy = find(y);
if (fx == fy) {
return;
}
father[fx] = fy;
// 合并集合，更新集合的元素个数
size[fy] += size[fx];
}
}