并查集知识
首先介绍一下并查集。并查集主要用于解决一些元素分组的问题。它管理一系列不相交的集合，并支持两种操作：
- 合并（Union）：把两个不相交的集合合并为一个集合。
- 查询（Find）：查询两个元素是否在同一个集合中。
初始化
在初始状态下，每个元素的父节点都是自己，代表每个元素单独一个分组。
int[] p = new int[n];
for(int i = 0; i < n; i++) {
p[i] = i;
}
查询
查询的效果是找到元素的祖先节点，如果两个元素的祖先节点相同，则它们在同一个集合中。
注意下面的查询使用了路径压缩的技巧。（即将元素的父节点设置为祖先节点，减少后续的搜索次数）
private int find(int m) {
// 这里使用了路径压缩
if(p[m] != m) {
p[m] = find(p[m]);
}
return p[m];
}
合并
合并一定要注意的是合并的是集合，而不是单个元素，关键是合并两个元素的祖先节点。
private void merge(int i, int j)
{
p[find(i)] = find(j);
}
知道了并查集的查用操作，我们就可以用它解决问题了。
题目描述
给你一个整数 n ，表示有 n 个专家从 0 到 n - 1 编号。另外给你一个下标从 0 开始的二维整数数组 meetings ，其中 meetings[i] = [xi, yi, timei] 表示专家 xi 和专家 yi 在时间 timei 要开一场会。一个专家可以同时参加 多场会议 。最后，给你一个整数 firstPerson 。
专家 0 有一个 秘密 ，最初，他在时间 0 将这个秘密分享给了专家 firstPerson 。接着，这个秘密会在每次有知晓这个秘密的专家参加会议时进行传播。更正式的表达是，每次会议，如果专家 xi 在时间 timei 时知晓这个秘密，那么他将会与专家 yi 分享这个秘密，反之亦然。
秘密共享是 瞬时发生 的。也就是说，在同一时间，一个专家不光可以接收到秘密，还能在其他会议上与其他专家分享。
在所有会议都结束之后，返回所有知晓这个秘密的专家列表。你可以按 任何顺序 返回答案。
思路分析
每次分享秘密，可以看作把两个专家合并到一个集合中，因此采用并查集求解。
最开始，每个专家的祖先节点记为自己，由于秘密传播是通过会议进行的，时间靠后的会议不可能传播到时间靠前的会议，因此需要先对meetings数组按照会议时间排序。
排序完成后，遍历所有时刻。同一时刻可能存在多场会议，由于秘密共享是瞬时发生的，且同一时刻的会议是乱序的，不存在先后，所以对每一时刻的处理分为两步：
-
第一轮遍历：首先判断两位专家中是否有人知道秘密，若有人知道秘密，则将两位专家的祖先节点都置为0。另外，无论两位专家是否有人知道秘密，都要将两个专家合并，因为同一时刻的其他会议中，可能有其他知道秘密的专家将秘密分享给这两位中的任何一个。
-
第二轮遍历：处理两种情况，
-
场景一：第一轮遍历中，先遍历到某场会议，此时两位专家都不知道秘密，但在后面的遍历中，其中一位专家知道了秘密，由于上一步做了合并集合处理，此时将两位专家的祖先节点均置为0即可。
-
场景二：第一轮遍历中，先遍历到某场会议，此时两位专家都不知道秘密，在后面的遍历中，这两位专家均没有被分享秘密，这时需要将两位专家从合并的集合中分离出来，如果不分离出来，在后面某时刻，如果这两位专家其中一个知道了秘密，那么会认为这两位专家都知道了秘密，但事实上，由于该时刻已过去，秘密无法分享给另一位专家。
-
Java 代码
class Solution {
private int[] p; //并查集
public List<Integer> findAllPeople(int n, int[][] meetings, int firstPerson) {
// treeMap，key是时间
TreeMap<Integer, List<int[]>> treeMap = new TreeMap<>();
for(int[] meeting : meetings) {
int key = meeting[2];
if(treeMap.containsKey(key)) {
treeMap.get(key).add(meeting);
} else {
List<int[]> list = new ArrayList<>();
list.add(meeting);
treeMap.put(key, list);
}
}
// 设置并查集
p = new int[n];
for(int i = 0; i< n; i++) {
p[i] = i;
}
// 知晓秘密的专家父节点设为0
p[firstPerson] = 0;
for(Map.Entry<Integer, List<int[]>> entry : treeMap.entrySet()) {
// 第一轮遍历，合并
for(int[] meeting : entry.getValue()) {
if(find(meeting[0]) == 0 || find(meeting[1]) == 0) {
p[find(meeting[0])] = 0;
p[find(meeting[1])] = 0;
} else {
p[find(meeting[0])] = find(meeting[1]);
}
}
// 第二轮遍历，对知晓秘密和不知晓秘密的专家分别处理
for(int[] meeting : entry.getValue()) {
if(find(meeting[0]) == 0 || find(meeting[1]) == 0) {
p[find(meeting[0])] = 0;
p[find(meeting[1])] = 0;
} else {
// 注意这里要将不知晓秘密的专家还原
p[meeting[0]] = meeting[0];
p[meeting[1]] = meeting[1];
}
}
}
List<Integer> r = new ArrayList<>();
for(int i = 0; i < n; i++) {
if(find(i) == 0) {
r.add(i);
}
}
return r;
}
// 查找父节点
private int find(int m) {
// 这里使用了路径压缩
if(p[m] != m) {
p[m] = find(p[m]);
}
return p[m];
}
}
网友评论