class Solution {
public:
vector<int> findAllPeople(int n, vector<vector<int>>& meetings, int firstPerson) {
}
};
2092. 找出知晓秘密的所有专家
给你一个整数 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 <= 1051 <= meetings.length <= 105meetings[i].length == 30 <= xi, yi <= n - 1xi != yi1 <= timei <= 1051 <= firstPerson <= n - 1原站题解
python3 解法, 执行用时: 496 ms, 内存消耗: 60.4 MB, 提交时间: 2023-10-10 15:39:36
class Solution:
def findAllPeople(self, n: int, meetings: List[List[int]], firstPerson: int) -> List[int]:
m = len(meetings)
meetings.sort(key=lambda x: x[2])
secret = [False] * n
secret[0] = secret[firstPerson] = True
i = 0
while i < m:
# meetings[i .. j] 为同一时间
j = i
while j + 1 < m and meetings[j + 1][2] == meetings[i][2]:
j += 1
vertices = set()
edges = defaultdict(list)
for k in range(i, j + 1):
x, y = meetings[k][0], meetings[k][1]
vertices.update([x, y])
edges[x].append(y)
edges[y].append(x)
q = deque([u for u in vertices if secret[u]])
while q:
u = q.popleft()
for v in edges[u]:
if not secret[v]:
secret[v] = True
q.append(v)
i = j + 1
ans = [i for i in range(n) if secret[i]]
return ans
java 解法, 执行用时: 128 ms, 内存消耗: 107 MB, 提交时间: 2023-10-10 15:38:55
class Solution {
// 并查集数组，记录每个元素的祖先节点
public int[] p;
// 查找每个元素的祖先，（路径压缩，并查集模板）
public int find(int x) {
if (p[x] != x) p[x] = find(p[x]);
return p[x];
}
public List<Integer> findAllPeople(int n, int[][] meetings, int firstPerson) {
p = new int[n+1];
// 祖先数组初始化，将每个元素的祖先标记为自己
for (int i = 1; i <= n; ++ i) p[i] = i;
// 合并0号专家与firstPerson
p[firstPerson] = 0;
Map<Integer, List<int[]>> map = new TreeMap<>();
// 构造以时刻为key，会议列表为value的Map，TreeMap将自动按照key升序排序
for (int[] m : meetings) {
// m[2]为会议时刻，每个时刻对应多场会议
List<int[]> list = map.getOrDefault(m[2], new ArrayList<>());
list.add(m);
map.put(m[2], list);
}
// 对于每个时刻，遍历两次
for (int x : map.keySet()) {
// 第一轮遍历，合并集合
for (int[] l : map.get(x)) {
int a = l[0], b = l[1];
if (p[find(a)] == 0 || p[find(b)] == 0) { p[find(a)] = 0; p[find(b)] = 0; }
p[find(b)] = p[find(a)];
}
// 第二轮遍历，分场景讨论
for (int[] l : map.get(x)) {
int a = l[0], b = l[1];
// 场景一：两位专家在前面的会议均不知道秘密，后面遍历中其中一位专家知道了秘密，瞬时共享，两人都将知道秘密
if (p[find(a)] == 0 || p[find(b)] == 0) { p[find(a)] = 0; p[find(b)] = 0; }
// 场景二：两位专家在该时刻始终都不知道秘密，将合并的集合分离开，防止后面时刻有一个专家知道秘密，将秘密分享给另一个专家
else { p[a] = a; p[b] = b; }
}
}
List<Integer> ans = new ArrayList<>();
// 祖先为0的元素即为知道秘密的专家
for (int i = 0; i < n; ++ i) {
if (p[find(i)] == 0) ans.add(i);
}
return ans;
}
}
cpp 解法, 执行用时: 576 ms, 内存消耗: 129.6 MB, 提交时间: 2023-10-10 15:38:33
// 并查集模板
class UnionFind {
public:
vector<int> parent;
vector<int> size;
int n;
// 当前连通分量数目
int setCount;
public:
UnionFind(int _n): n(_n), setCount(_n), parent(_n), size(_n, 1) {
iota(parent.begin(), parent.end(), 0);
}
int findset(int x) {
return parent[x] == x ? x : parent[x] = findset(parent[x]);
}
bool unite(int x, int y) {
x = findset(x);
y = findset(y);
if (x == y) {
return false;
}
if (size[x] < size[y]) {
swap(x, y);
}
parent[y] = x;
size[x] += size[y];
--setCount;
return true;
}
bool connected(int x, int y) {
x = findset(x);
y = findset(y);
return x == y;
}
void isolate(int x) {
if(x != parent[x]){
parent[x] = x;
size[x] = 1;
++setCount;
}
}
};
bool cmp(const vector<int>& a, const vector<int>& b){
return a[2]<b[2];
}
class Solution {
public:
vector<int> findAllPeople(int n, vector<vector<int>>& ms, int fp) {
sort(ms.begin(), ms.end(), cmp);
int m = ms.size();
UnionFind uf(n);
uf.unite(fp, 0);
for(int i=0;i<m;i++){
int j = i+1;
while(j < m){
if(ms[i][2] != ms[j][2]){
break;
}
j++;
}
for(int k=i;k<j;k++){
uf.unite(ms[k][0], ms[k][1]);
}
for(int k=i;k<j;k++){
if(!uf.connected(ms[k][0], 0)){
uf.isolate(ms[k][0]);
uf.isolate(ms[k][1]);
}
}
i=j-1;
}
vector<int>ans;
for(int i=0;i<n;i++){
if(uf.connected(i, 0)){
ans.push_back(i);
}
}
return ans;
}
};
cpp 解法, 执行用时: 984 ms, 内存消耗: 242.5 MB, 提交时间: 2023-10-10 15:37:43
class Solution {
public:
vector<int> findAllPeople(int n, vector<vector<int>>& meetings, int firstPerson) {
sort(meetings.begin(),meetings.end(),[&](const auto &v1,const auto &v2){return v1[2]<v2[2];});
unordered_set<int> haveSecret={0,firstPerson};
int m=meetings.size();
for (int i=0;i<m;){
unordered_map<int,vector<int>> g;
int time=meetings[i][2];
for (;i<m&&meetings[i][2]==time;i++){
int a=meetings[i][0],b=meetings[i][1];
g[a].push_back(b);
g[b].push_back(a);
}
function<void(int)> dfs=[&](int v){
haveSecret.insert(v);
for (int& w:g[v])
if (!haveSecret.count(w))
dfs(w);
};
for (auto &[v,_]:g)
if (haveSecret.count(v))
dfs(v);
}
vector<int> ans;
for (auto &v:haveSecret)
ans.push_back(v);
return ans;
}
};
python3 解法, 执行用时: 400 ms, 内存消耗: 75.1 MB, 提交时间: 2023-10-10 15:37:26
class Solution:
def findAllPeople(self, n: int, meetings: List[List[int]], firstPerson: int) -> List[int]:
meetings.sort(key=lambda x: x[2])
ans = {0, firstPerson}
for _, members in groupby(meetings, key=lambda x: x[2]):
graph = defaultdict(list)
for x, y, _ in members:
if x in ans and y in ans:
continue
graph[x].append(y)
graph[y].append(x)
def dfs(node):
visited.add(node)
ans.add(node)
for nei in graph[node]:
if nei not in visited:
dfs(nei)
visited = set()
for already_known in graph:
if already_known in ans and already_known not in visited:
dfs(already_known)
return list(ans)
golang 解法, 执行用时: 376 ms, 内存消耗: 37.8 MB, 提交时间: 2023-10-10 15:36:35
func findAllPeople(_ int, meetings [][]int, firstPerson int) (ans []int) {
sort.Slice(meetings, func(i, j int) bool { return meetings[i][2] < meetings[j][2] }) // 按照时间排序
haveSecret := map[int]bool{0: true, firstPerson: true} // 一开始 0 和 firstPerson 都知道秘密
for i, m := 0, len(meetings); i < m; {
g := map[int][]int{}
time := meetings[i][2]
// 遍历时间相同的会议。注意这里的 i 和外层循环的 i 是同一个变量，所以整个循环部分的时间复杂度是线性的
for ; i < m && meetings[i][2] == time; i++ {
v, w := meetings[i][0], meetings[i][1]
g[v] = append(g[v], w) // 建图
g[w] = append(g[w], v)
}
vis := map[int]bool{} // 避免重复访问专家
var dfs func(int)
dfs = func(v int) {
vis[v] = true
haveSecret[v] = true
for _, w := range g[v] {
if !vis[w] {
dfs(w)
}
}
}
for v := range g {
if haveSecret[v] && !vis[v] { // 从在图上且知道秘密的专家出发，DFS 标记所有能到达的专家
dfs(v)
}
}
}
for i := range haveSecret {
ans = append(ans, i) // 注意可以按任何顺序返回答案
}
return
}