2092. 找出知晓秘密的所有专家

1. 辅助类：并查集 (UnionFind)

这是一个标准的并查集实现，用于维护元素之间的集合关系（连通性）。

• fa (父节点数组): fa[i] 存储节点 i 的父节点。
• 构造函数: ranges::iota(fa, 0) 将数组初始化为 [0, 1, 2, ..., n-1]，即一开始每个人都是自己的代表，互不相连。
• find(x): 查找 x 的根节点（代表元）。使用了路径压缩（fa[x] = find(fa[x])），这能让后续的查找非常快，接近 $O(1)$。
• merge(from, to): 将两个集合合并。
• is_same(x, y): 判断两个人是否属于同一个集合（即是否通过某种路径相连）。

2. 核心逻辑 (findAllPeople)

第一步：预处理

// 按照 time 从小到大排序
ranges::sort(meetings, {}, [](auto& a) { return a[2]; });UnionFind uf(n);
// 一开始 0 和 firstPerson 都知道秘密
uf.merge(firstPerson, 0);

• 排序： 秘密是按时间传播的。如果 T=10 知道了秘密，不能传播给 T=5 开会的人。所以必须按时间升序处理。
• 初始状态： 0号专家是秘密源头，firstPerson 也在第一时间知道。将他们合并到同一个集合中（我们可以把与 0 连通的集合称为“知情组”）。

第二步：分组循环（处理同一时间的会议）

这是算法最精彩的部分。它处理了同一时刻秘密的瞬间传播。

int m = meetings.size();
for (int i = 0; i < m;) {int start = i;int time = meetings[i][2];// 1. 合并在同一时间发生的会议 (乐观合并)for (; i < m && meetings[i][2] == time; i++) {uf.merge(meetings[i][0], meetings[i][1]);}// 2. 检查并撤销无效合并 (断开未连通 0 的人)for (int j = start; j < i; j++) {int x = meetings[j][0], y = meetings[j][1];if (!uf.is_same(x, 0)) {uf.fa[x] = x; // 孤立 x}if (!uf.is_same(y, 0)) {uf.fa[y] = y; // 孤立 y}}
}

逻辑详解：

1. 找出同一时刻的所有会议： 内层的 for 循环把所有时间为 time 的会议都找出来。
2. 全部合并（乐观策略）： 在这个时刻，不管谁知道秘密，先把开会的人都连起来。
   • 例如：0知道秘密。会议有 [0, A], [B, C]。
   • 合并后：{0, A} 连通，{B, C} 连通。
3. 撤销（Reset）逻辑 —— 最关键的一步：
   • 遍历刚才合并过的所有人。检查他们现在是否和 0 号连通。
   • 如果在同一个集合（is_same(x, 0) 为真）： 说明这个人通过这一批会议，成功链式接触到了秘密源头，他现在的状态是“知情”，保留合并关系。
   • 如果不在同一个集合： 说明这几个人虽然在当前时刻开会了（比如 B 和 C 开会），但他们中没有人知道秘密。
     • 必须把他们重置为孤立状态 (uf.fa[x] = x)。
     • 为什么？ 因为秘密不会“预知未来”或“穿越回过去”。如果 B 和 C 在 T=5 开会（都不知道秘密），而在 T=10 时 B 遇到了 0 知道了秘密，此时 T=5 的那次会议不能让 C 也知道秘密。如果现在不把 B 和 C 断开，等到 T=10 处理 B 时，C 也会顺带被判定为知情，这是错误的。

第三步：收集结果

vector<int> ans;
for (int i = 0; i < n; i++) {if (uf.is_same(i, 0)) { // 只要和 0 连通，就是知情人ans.push_back(i);}
}
return ans;

最后扫描所有人，只要和 0 号专家在同一个集合，就加入结果列表。

---

总结

这个算法非常巧妙地解决了“动态连通性”的一个特例：

1. 时间维度： 通过排序解决。
2. 空间传播： 通过并查集解决。
3. 状态隔离： 通过“同一时间批处理 -> 检查连通性 -> 只有未连通源头的重置”这一策略，避免了错误的秘密传播，同时保证了同一时刻的秘密能瞬间传遍整个连通分量。

复杂度分析：

• 时间复杂度： $O(M \log M + M \alpha(N))$。主要是排序的开销，并查集的操作接近常数。
• 空间复杂度： $O(N)$，用于并查集数组。