网站建设都有什么工作要做,新闻摘抄四年级下册,公司组织机构框架图,wordpress目录upgrade文章目录1. 题目2. 解题1. 题目
给你一个整数 n #xff0c;表示有 n 个专家从 0 到 n - 1 编号。 另外给你一个下标从 0 开始的二维整数数组 meetings #xff0c;其中 meetings[i] [xi, yi, timei] 表示专家 xi 和专家 yi 在时间 timei 要开一场会。 一个专家可以同时参加…
文章目录1. 题目2. 解题1. 题目
给你一个整数 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 都将知晓这个秘密。示例 4
输入n 6, meetings [[0,2,1],[1,3,1],[4,5,1]], firstPerson 1
输出[0,1,2,3]
解释
时间 0 专家 0 将秘密与专家 1 共享。
时间 1 专家 0 将秘密与专家 2 共享专家 1 将秘密与专家 3 共享。
因此在所有会议结束后专家 0、1、2 和 3 都将知晓这个秘密。提示
2 n 10^5
1 meetings.length 10^5
meetings[i].length 3
0 xi, yi n - 1
xi ! yi
1 timei 10^5
1 firstPerson n - 1来源力扣LeetCode 链接https://leetcode-cn.com/problems/find-all-people-with-secret 著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。 2. 解题
参考数据结构 并查集
按时间对会议进行排序对相同时间进行的会议进行并查集合并操作之后再次检查对不知道秘密的专家撤销合并操作之前不知道这个导致一直超时
class dsu{
public:vectorint f;dsu(int n){f.resize(n);for(int i 0; i n; i)f[i] i;}void merge(int a, int b){int fa find(a), fb find(b);f[fa] fb;}int find(int a){if(a f[a]) return a;return f[a] find(f[a]);}void unmerge(int a){f[a] a;}
};
class Solution {
public:vectorint findAllPeople(int n, vectorvectorint meetings, int firstPerson) {int mlen meetings.size();vectorbool known(n, false);known[0] known[firstPerson] true;sort(meetings.begin(), meetings.end(),[](auto a, auto b){return a[2] b[2];});dsu uset(n);for(int i 0; i mlen; ){int t meetings[i][2], j i;while(j mlen meetings[j][2]t){ // 时间相同的会议int a meetings[j][0], b meetings[j][1];int f1 uset.find(a);int f2 uset.find(b);if(known[f2]) // b 知道秘密uset.merge(a, b);//有顺序的注意elseuset.merge(b, a);j;}for(int k i; k j; k){int a meetings[k][0], b meetings[k][1];int f1 uset.find(a);int f2 uset.find(b);if(known[f1] || known[f2])known[a]known[b]true;else{ // 两人都不知道秘密恢复他们的初始状态uset.unmerge(a);uset.unmerge(b);}}i j;}vectorint ans;for(int i 0; i n; i)if(known[i])ans.push_back(i);return ans;}
};600 ms 130.9 MB C 我的CSDN博客地址 https://michael.blog.csdn.net/
长按或扫码关注我的公众号Michael阿明一起加油、一起学习进步
