推荐|【图论】【广度优先】【并集查找】2092 找出知晓秘密的所有专家

本文涉及知识点

图论深度优先广度优先并集查找

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 <= 10⁵
1 <= meetings.length <= 10⁵
meetings[i].length == 3
0 <= xi, yi <= n - 1
xi != yi
1 <= timei <= 10⁵
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& meetings, int firstPerson) {
std::unordered_set setHasKnow;
setHasKnow.emplace(0);
setHasKnow.emplace(firstPerson);
std::map>> mTimePer;
for (const auto& v : meetings)
{
mTimePer[v[2]].emplace_back(v[0],v[1]);
}
for (const auto& it : mTimePer)
{
std::unordered_map 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

我想对大家说的话
闻缺陷则喜是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。
子墨子言之：事无终始，无务多业。也就是我们常说的专业的人做专业的事。
如果程序是一条龙，那算法就是他的是睛

测试环境

操作系统：win7 开发环境： VS2019 C++17
或者操作系统：win10 开发环境： VS2022 C++17
如无特殊说明，本算法用**C++**实现。

文章知识点与官方知识档案匹配，可进一步学习相关知识

算法技能树首页概览60496 人正在系统学习中

群中有博文配套源码

QQ群名片