2092. 寻找拥有秘密的所有人

Hard

题目描述

给你一个整数 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]

示例 3：

输入： n = 5, meetings = [[3,4,2],[1,2,1],[2,3,1]], firstPerson = 1
输出： [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

解题思路

这道题可以用并查集（Union-Find）来解决，核心思路是按时间顺序处理会议，对于同一时间的会议构建连通图。

主要思路：

时间分组：将所有会议按时间分组，因为秘密在同一时间内可以瞬时传播
并查集维护连通性：对于每个时间点的会议，使用并查集来维护人员之间的连通关系
秘密传播判断：检查每个连通分量是否包含已知秘密的人员，如果包含则整个分量都知道秘密
重置连接：处理完每个时间点后，需要重置那些不知道秘密的人员的连接关系

算法步骤：

初始化并查集，标记人员0和firstPerson知道秘密
按时间排序并分组处理会议
对于每个时间的会议：建立连通关系 → 传播秘密 → 重置不知秘密者的连接
返回所有知道秘密的人员列表

时间复杂度分析： 虽然看起来复杂，但每个人员最多被重置常数次，总体复杂度为O(M×α(N))，其中α是反阿克曼函数。

代码实现

class Solution {
public:
    vector<int> findAllPeople(int n, vector<vector<int>>& meetings, int firstPerson) {
        vector<int> parent(n), rank(n, 0);
        iota(parent.begin(), parent.end(), 0);
        vector<bool> hasSecret(n, false);
        hasSecret[0] = hasSecret[firstPerson] = true;
        
        function<int(int)> find = [&](int x) {
            return parent[x] == x ? x : parent[x] = find(parent[x]);
        };
        
        auto unite = [&](int x, int y) {
            int px = find(x), py = find(y);
            if (px == py) return;
            if (rank[px] < rank[py]) swap(px, py);
            parent[py] = px;
            if (rank[px] == rank[py]) rank[px]++;
        };
        
        sort(meetings.begin(), meetings.end(), [](const vector<int>& a, const vector<int>& b) {
            return a[2] < b[2];
        });
        
        int i = 0;
        while (i < meetings.size()) {
            int currentTime = meetings[i][2];
            vector<int> people;
            
            while (i < meetings.size() && meetings[i][2] == currentTime) {
                people.push_back(meetings[i][0]);
                people.push_back(meetings[i][1]);
                unite(meetings[i][0], meetings[i][1]);
                i++;
            }
            
            sort(people.begin(), people.end());
            people.erase(unique(people.begin(), people.end()), people.end());
            
            for (int person : people) {
                if (hasSecret[find(person)]) {
                    for (int p : people) {
                        if (find(p) == find(person)) {
                            hasSecret[p] = true;
                        }
                    }
                }
            }
            
            for (int person : people) {
                if (!hasSecret[person]) {
                    parent[person] = person;
                    rank[person] = 0;
                }
            }
        }
        
        vector<int> result;
        for (int i = 0; i < n; i++) {
            if (hasSecret[i]) result.push_back(i);
        }
        return result;
    }
};

class Solution:
    def findAllPeople(self, n: int, meetings: List[List[int]], firstPerson: int) -> List[int]:
        parent = list(range(n))
        rank = [0] * n
        has_secret = [False] * n
        has_secret[0] = has_secret[firstPerson] = True
        
        def find(x):
            if parent[x] != x:
                parent[x] = find(parent[x])
            return parent[x]
        
        def unite(x, y):
            px, py = find(x), find(y)
            if px == py:
                return
            if rank[px] < rank[py]:
                px, py = py, px
            parent[py] = px
            if rank[px] == rank[py]:
                rank[px] += 1
        
        meetings.sort(key=lambda x: x[2])
        
        i = 0
        while i < len(meetings):
            current_time = meetings[i][2]
            people = []
            
            while i < len(meetings) and meetings[i][2] == current_time:
                people.extend([meetings[i][0], meetings[i][1]])
                unite(meetings[i][0], meetings[i][1])
                i += 1
            
            people = list(set(people))
            
            for person in people:
                if has_secret[find(person)]:
                    for p in people:
                        if find(p) == find(person):
                            has_secret[p] = True
            
            for person in people:
                if not has_secret[person]:
                    parent[person] = person
                    rank[person] = 0
        
        return [i for i in range(n) if has_secret[i]]

public class Solution {
    public IList<int> FindAllPeople(int n, int[][] meetings, int firstPerson) {
        int[] parent = new int[n];
        int[] rank = new int[n];
        bool[] hasSecret = new bool[n];
        
        for (int i = 0; i < n; i++) {
            parent[i] = i;
        }
        hasSecret[0] = hasSecret[firstPerson] = true;
        
        int Find(int x) {
            if (parent[x] != x) {
                parent[x] = Find(parent[x]);
            }
            return parent[x];
        }
        
        void Unite(int x, int y) {
            int px = Find(x), py = Find(y);
            if (px == py) return;
            if (rank[px] < rank[py]) {
                (px, py) = (py, px);
            }
            parent[py] = px;
            if (rank[px] == rank[py]) rank[px]++;
        }
        
        Array.Sort(meetings, (a, b) => a[2].CompareTo(b[2]));
        
        int i = 0;
        while (i < meetings.Length) {
            int currentTime = meetings[i][2];
            var people = new HashSet<int>();
            
            while (i < meetings.Length && meetings[i][2] == currentTime) {
                people.Add(meetings[i][0]);
                people.Add(meetings[i][1]);
                Unite(meetings[i][0], meetings[i][1]);
                i++;
            }
            
            foreach (int person in people) {
                if (hasSecret[Find(person)]) {
                    foreach (int p in people) {
                        if (Find(p) == Find(person)) {
                            hasSecret[p] = true;
                        }
                    }
                }
            }
            
            foreach (int person in people) {
                if (!hasSecret[person]) {
                    parent[person] = person;
                    rank[person] = 0;
                }
            }
        }
        
        var result = new List<int>();
        for (int j = 0; j < n; j++) {
            if (hasSecret[j]) result.Add(j);
        }
        return result;
    }
}

var findAllPeople = function(n, meetings, firstPerson) {
    const hasSecret = new Set([0, firstPerson]);
    
    // Group meetings by time
    const meetingsByTime = new Map();
    for (const [x, y, time] of meetings) {
        if (!meetingsByTime.has(time)) {
            meetingsByTime.set(time, []);
        }
        meetingsByTime.get(time).push([x, y]);
    }
    
    // Sort times
    const times = Array.from(meetingsByTime.keys()).sort((a, b) => a - b);
    
    for (const time of times) {
        const currentMeetings = meetingsByTime.get(time);
        
        // Build adjacency list for current time
        const adj = new Map();
        const people = new Set();
        
        for (const [x, y] of currentMeetings) {
            if (!adj.has(x)) adj.set(x, []);
            if (!adj.has(y)) adj.set(y, []);
            adj.get(x).push(y);
            adj.get(y).push(x);
            people.add(x);
            people.add(y);
        }
        
        // Find connected components and spread secret
        const visited = new Set();
        
        for (const person of people) {
            if (!visited.has(person)) {
                const component = [];
                const queue = [person];
                visited.add(person);
                
                while (queue.length > 0) {
                    const curr = queue.shift();
                    component.push(curr);
                    
                    if (adj.has(curr)) {
                        for (const neighbor of adj.get(curr)) {
                            if (!visited.has(neighbor)) {
                                visited.add(neighbor);
                                queue.push(neighbor);
                            }
                        }
                    }
                }
                
                // If any person in component has secret, give it to all
                const hasSecretInComponent = component.some(p => hasSecret.has(p));
                if (hasSecretInComponent) {
                    for (const p of component) {
                        hasSecret.add(p);
                    }
                }
            }
        }
    }
    
    return Array.from(hasSecret).sort((a, b) => a - b);
};

在 LeetCode 上运行：力扣中文版 LeetCode 国际版

复杂度分析

复杂度	大小
时间复杂度	O(M × α(N))
空间复杂度	O(N + M)

其中 N 是人员数量，M 是会议数量，α 是反阿克曼函数。

题目描述#

解题思路#

代码实现#

复杂度分析#

相关题目#

题目描述

解题思路

代码实现

复杂度分析

相关题目