leetcode 2092(排序+bfs)

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

思路：排序+bfs广度优先搜索

假设一开始 0 和 1 知道秘密。对比如下两种情况：

• 时间 1，1 和 2 开会。时间 2，2 和 3 开会。秘密会传播给 2 和 3，最终 0,1,2,3 都知道秘密。
• 时间 1，2 和 3 开会。时间 2，1 和 2 开会。第一场会议，参加会议的人都不知道秘密，所以秘密不会传播。秘密只会在第二场会议传播给 2，最终 0,1,2 都知道秘密。

所以要按照开会的先后顺序传播秘密，模拟这个过程。

注意题目的这段话：

• 秘密共享是瞬时发生的。也就是说，在同一时间，一个专家不光可以接收到秘密，还能在其他会议上与其他专家分享。

解读：在同一时间发生的所有会议，可以视作一个无向图。专家是图中的节点，meetings[i] 是图的边，连接 xi 和 yi。这个图可能有多个连通块。每个连通块只要有一个人知道秘密，那么整个连通块的人都能知道秘密。

class Solution { public: vector<int> findAllPeople(int n, vector<vector<int>>& meetings, int firstPerson) { //按时间分组，同一时间的会议放一个 vector 里 map<int,vector<pair<int,int>>> met_time; for(auto& m:meetings) met_time[m[2]].emplace_back(m[0],m[1]); set<int> known{0,firstPerson}; //已知秘密的人 //按时间顺序处理，map容器自动升序排序 for(auto& [_,vec]:met_time){ unordered_map<int,vector<int>> g; set<int> nodes; //自动去重 //建图 for(auto& [u,v]:vec){ g[u].push_back(v); g[v].push_back(u); nodes.insert(u); nodes.insert(v); } //把当前时刻已知的所有人当起点做 BFS queue<int> q; for(int x:nodes) if(known.count(x)) q.push(x); while(!q.empty()){ int u=q.front();q.pop(); for(int v:g[u]){ if(!known.count(v)){ known.insert(v); q.push(v); } } } } vector<int> ans(known.begin(), known.end()); return ans; } };