本文涉及知识点
图论 深度优先 广度优先 并集查找
LeetCode2092. 找出知晓秘密的所有专家
给你一个整数 n ，表示有 n 个专家从 0 到 n - 1 编号。另外给你一个下标从 0 开始的二维整数数组 meetings ，其中 meetings[i] = [xi, yi, timei] 表示专家 xi 和专家 yi 在时间 timei 要开一场会。一个专家可以同时参加 多场会议 。最后，给你一个整数 firstPerson 。
专家 0 有一个 秘密 ，最初，他在时间 0 将这个秘密分享给了专家 firstPerson 。接着，这个秘密会在每次有知晓这个秘密的专家参加会议时进行传播。更正式的表达是，每次会议，如果专家 xi 在时间 timei 时知晓这个秘密，那么他将会与专家 yi 分享这个秘密，反之亦然。
秘密共享是 瞬时发生 的。也就是说，在同一时间，一个专家不光可以接收到秘密，还能在其他会议上与其他专家分享。
在所有会议都结束之后，返回所有知晓这个秘密的专家列表。你可以按 任何顺序 返回答案。
示例 1：
输入：n = 6, meetings = [[1,2,5],[2,3,8],[1,5,10]], firstPerson = 1
输出：[0,1,2,3,5]
解释：
时间 0 ，专家 0 将秘密与专家 1 共享。
时间 5 ，专家 1 将秘密与专家 2 共享。
时间 8 ，专家 2 将秘密与专家 3 共享。
时间 10 ，专家 1 将秘密与专家 5 共享。
因此，在所有会议结束后，专家 0、1、2、3 和 5 都将知晓这个秘密。
示例 2：
输入：n = 4, meetings = [[3,1,3],[1,2,2],[0,3,3]], firstPerson = 3
输出：[0,1,3]
解释：
时间 0 ，专家 0 将秘密与专家 3 共享。
时间 2 ，专家 1 与专家 2 都不知晓这个秘密。
时间 3 ，专家 3 将秘密与专家 0 和专家 1 共享。
因此，在所有会议结束后，专家 0、1 和 3 都将知晓这个秘密。
示例 3：
输入：n = 5, meetings = [[3,4,2],[1,2,1],[2,3,1]], firstPerson = 1
输出：[0,1,2,3,4]
解释：
时间 0 ，专家 0 将秘密与专家 1 共享。
时间 1 ，专家 1 将秘密与专家 2 共享，专家 2 将秘密与专家 3 共享。
注意，专家 2 可以在收到秘密的同一时间分享此秘密。
时间 2 ，专家 3 将秘密与专家 4 共享。
因此，在所有会议结束后，专家 0、1、2、3 和 4 都将知晓这个秘密。
提示：
2 <= n <= 105
1 <= meetings.length <= 105
meetings[i].length == 3
0 <= xi, yi <= n - 1
xi != yi
1 <= timei <= 105
1 <= firstPerson <= n - 1
题解
同一时间开会的专家，看成一条边。用并集查找或广度优先，看那些专家知晓密码。
我们平时封装的类，一般是复杂度是O(n)，无论有多少边。
极端情况下timei各不相同。时间复杂度变成了 O(nn)，超时。
用哈希映射重新实现并集查找或深度优先。时间复杂度:O(n)。
代码
class Solution { public: vector<int> findAllPeople(int n, vector<vector<int>>& meetings, int firstPerson) { m_vKnow.resize(n); m_vKnow[0] = m_vKnow[firstPerson] = true; sort(meetings.begin(), meetings.end(), [](const auto& v1, const auto& v2) {return v1[2] < v2[2]; }); for (int i = 0; i < meetings.size(); ) { int j = i; unordered_map<int, vector<int>> vNeiBo; for (; (j < meetings.size()) && (meetings[i][2] == meetings[j][2]); j++) { vNeiBo[meetings[j][0]].emplace_back(meetings[j][1]); vNeiBo[meetings[j][1]].emplace_back(meetings[j][0]); } BFS(vNeiBo); i = j; } vector<int> vRet; for (int i = 0; i < n; i++) { if (m_vKnow[i]) { vRet.emplace_back(i); } } return vRet; } void BFS(unordered_map<int, vector<int>>& vNeiBo) { queue<int> que; unordered_set<int> hasDo; auto Add = [&](int cur) { if (hasDo.count(cur)) { return; } hasDo.emplace(cur); que.emplace(cur); m_vKnow[cur] = true; }; for (const auto& [cur, v] : vNeiBo) { if (m_vKnow[cur]) { Add(cur); } } while (que.size()) { const auto cur = que.front(); que.pop(); for (const auto& next : vNeiBo[cur]) { Add(next); } } } vector<bool> m_vKnow; };
测试用例
template<class T, class T2> void Assert(const T& t1, const T2& t2) { assert(t1 == t2); } template<class T> void Assert(const vector<T>& v1, const vector<T>& v2) { if (v1.size() != v2.size()) { assert(false); return; } for (int i = 0; i < v1.size(); i++) { Assert(v1[i], v2[i]); } } int main() { int n; vector<vector<int>> meetings; int firstPerson; { Solution sln; n = 6, meetings = { {1,2,5},{2,3,8},{1,5,10} }, firstPerson = 1; auto res = sln.findAllPeople(n, meetings, firstPerson); Assert({ 0,1,2,3,5 }, res); } { Solution sln; n = 4, meetings = { {3,1,3},{1,2,2},{0,3,3} }, firstPerson = 3; auto res = sln.findAllPeople(n, meetings, firstPerson); Assert({ 0,1,3 }, res); } { Solution sln; n = 5, meetings = { {3,4,2},{1,2,1},{2,3,1} }, firstPerson = 1; auto res = sln.findAllPeople(n, meetings, firstPerson); Assert({ 0,1,2,3,4 }, res); } }
2023年4月
class Solution { public: vector findAllPeople(int n, vector<vector>& meetings, int firstPerson) { std::unordered_set setHasKnow; setHasKnow.emplace(0); setHasKnow.emplace(firstPerson); std::map<int, vector<pair<int,int>>> mTimePer; for (const auto& v : meetings) { mTimePer[v[2]].emplace_back(v[0],v[1]); } for (const auto& it : mTimePer) { std::unordered_map<int, vector> mNeib; std::unordered_set setHasDo; for (const auto& per : it.second) { mNeib[per.first].emplace_back(per.second); mNeib[per.second].emplace_back(per.first); if (setHasKnow.count(per.first)) { setHasDo.emplace(per.first); } if (setHasKnow.count(per.second)) { setHasDo.emplace(per.second); } } std::queue que; for (const auto& s : setHasDo) { que.emplace(s); } while (que.size()) { int iCur = que.front(); que.pop(); for (const auto& next : mNeib[iCur]) { if (setHasDo.count(next)) { continue; } setHasKnow.emplace(next); setHasDo.emplace(next); que.emplace(next); } } } return vector(setHasKnow.begin(), setHasKnow.end()); } };
扩展阅读
视频课程
有效学习：明确的目标 及时的反馈 拉伸区（难度合适），可以先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的讲解。
https://edu.csdn.net/course/detail/38771
如何你想快速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176
相关
下载
想高屋建瓴的学习算法，请下载《喜缺全书算法册》doc版
https://download.csdn.net/download/he_zhidan/88348653
| 我想对大家说的话 |
| 闻缺陷则喜是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。 |
| 子墨子言之：事无终始，无务多业。也就是我们常说的专业的人做专业的事。 |
| 如果程序是一条龙，那算法就是他的是睛 |
测试环境
操作系统：win7 开发环境： VS2019 C++17
或者 操作系统：win10 开发环境： VS2022 C++17
如无特殊说明，本算法用**C++**实现。
