20240223-2092.查找所有有秘密的人

题目要求

给你一个整数 n，表示有 n 个人，编号从 0 到 n - 1。你还给你一个 0 索引的二维整数数组 meetings，其中 meetings[i] = [xi, yi, timei] 表示 xi 和 yi 在 timei 有一个会议。一个人可以同时参加多个会议。最后，给你一个整数 firstPerson。

人 0 有一个秘密，并在时间 0 开始与人 firstPerson 共享该秘密。更正式地说，在每次会面时，如果某人 xi 在时间 i 拥有该秘密，那么他将与某人 yi 共享该秘密，反之亦然。

秘密是即时共享的。也就是说，一个人收到秘密后，可以在同一时间内与其他会议上的人分享。

在所有会议结束后，返回所有拥有该秘密的人的名单。您可以按照任何顺序返回答案。

思路

我们需要找到所有会议结束之后（时间最后）拥有信息的人的名单，那么我们就需要将会议按照时间进行排序。

第二我们需要在同一会议时间判断出谁拥有秘密，谁在当前时间获得了秘密。然后这个过程继续传递直到时间结束。

在0时刻，编号为0和firstPerson的人获得了秘密。然后在之后的每一个时间点我们需要找到0和firstPerson和其他哪些人产生了交集，而后以此类推。

为了完成这一目的，根据建议我们应该采取并查集（Union-Find）的数据结构。

并查集是一种非常高效的数据结构，用于处理一些不交集的合并及查询问题，特别适用于本题中的场景，即追踪和管理一组动态集合的合并与查找操作。

并查集主要支持两种操作：

Find: 确定某个元素属于哪个集合，也就是这个元素的“根”是什么。在并查集中，每个集合由一个代表元素（根）来标识，所有属于同一集合的元素的根都是相同的。
Union: 将两个元素所在的集合合并为一个集合。这通常通过将一个集合的根元素连接到另一个集合的根元素来完成。

并查集通过数组或哈希表来实现，每个元素都有一个指向父元素的指针，根元素的指针指向它自己，这样形成一个树状结构。

基本操作的实现

初始化（Initialization）：一开始，每个人都在自己独立的集合中，也就是每个人都是自己集合的根。
查找（Find）：为了找到元素的根（代表元素），我们不断地追溯它的父元素，直到找到一个指向自己的元素，那就是根。在实际操作中，为了提高效率，我们会进行路径压缩，即在执行查找操作的同时，将查找路径上的所有元素直接连接到根上，这样可以减少后续查找操作的时间。
合并（Union）：当我们想要合并两个元素所在的集合时，我们首先找到它们各自的根，如果根不同，就将其中一个根的父元素设置为另一个根，从而将两个树合并为一棵。为了保持树的平衡，通常会使用按秩合并，即总是将较小的树连接到较大的树上。

代码

#include <algorithm>
#include <unordered_set>
class UnionFind {
public:vector<int> parent;vector<int> rank;UnionFind(int size) : parent(size), rank(size, 0) {for (int i = 0; i < size; ++i) {parent[i] = i;}}int find(int x) {if (x != parent[x]) {parent[x] = find(parent[x]);}return parent[x];}void unionSet(int x, int y) {int rootX = find(x);int rootY = find(y);if (rootX != rootY) {if (rank[rootX] < rank[rootY]) {parent[rootX] = rootY;} else if (rank[rootX] > rank[rootY]) {parent[rootY] = rootX;} else {parent[rootY] = rootX;rank[rootX]++;}}}
};
class Solution {
public:vector<int> findAllPeople(int n, vector<vector<int>>& meetings, int firstPerson) {UnionFind uf(n);uf.unionSet(0, firstPerson);sort(meetings.begin(), meetings.end(), [](const vector<int>& a, const vector<int>& b) {return a[2] < b[2];});vector<int> secretHolders;for (int i = 0; i < meetings.size(); ) {int time = meetings[i][2];unordered_set<int> thisTimeMeeting;while (i < meetings.size() && meetings[i][2] == time) {uf.unionSet(meetings[i][0], meetings[i][1]);thisTimeMeeting.insert(meetings[i][0]);thisTimeMeeting.insert(meetings[i][1]);i++;}for (int person : thisTimeMeeting) {if (uf.find(person) != uf.find(0)) {uf.parent[person] = person;}}}for (int i = 0; i < n; ++i) {if (uf.find(i) == uf.find(0)) {secretHolders.push_back(i);}}return secretHolders;}
};

时空复杂度

时间复杂度

空间复杂度

理解并查集

理解并查集的这种写法，我们可以分解为几个关键点：初始化、查找（Find）、合并（Union）以及路径压缩的实现。这些是并查集数据结构核心操作的实现，旨在高效处理动态连通性问题。

初始化（Constructor）

在并查集的构造函数中，每个元素最开始都指向自己，表示每个元素自成一个集合。rank数组用于记录每个根节点所在树的深度，有助于在执行合并操作时保持树的平衡，减少查找时间。

UnionFind(int size) : parent(size), rank(size, 0) {for(int i = 0; i < size; ++i) {parent[i] = i; // 每个节点的父节点指向自己}
}

查找（Find）

查找操作用于找到给定元素所在集合的根节点（代表元素）。路径压缩技术通过将查找路径上的每个节点直接链接到根节点，从而降低后续查找操作的复杂度。

int find(int x) {if(x != parent[x]) {parent[x] = find(parent[x]); // 路径压缩}return parent[x];
}

合并（Union）

合并操作用于将两个元素所在的集合合并为一个集合。它首先找到两个元素各自的根节点，如果根节点不同，说明它们属于不同的集合，需要合并。使用rank来决定如何合并，以保持树的平衡性，避免形成深度过大的树结构。

void unionSet(int x, int y) {int rootX = find(x);int rootY = find(y);if(rootX != rootY) {if(rank[rootX] < rank[rootY]) {parent[rootX] = rootY; // 将较浅的树的根节点指向较深的树的根节点} else if(rank[rootX] > rank[rootY]) {parent[rootY] = rootX;} else {parent[rootY] = rootX; // 如果深度相同，就选择一个作为根，增加其深度rank[rootX]++;}}
}