本篇题解需读者先掌握 DFS 基础知识。

1. 视为无向图，专家为顶点，能分享秘密的专家之间存在无向边。
2. 将 meetings 按时间分组且更早的组在前，每组皆改成邻接表。
3. 在同一时刻中我们针对已访问的顶点（知晓秘密的专家）和相应邻接表向外探索即可。

探索方式可以为 DFS, BFS, 并查集，本篇采用最简单的 DFS。

Code

###C++

class Solution {
private: 
    void dfs(int u, const unordered_map<int, vector<int>>& adj, vector<bool>& visited) {
        for (int v : adj.at(u)) {
            if (!visited[v]) {
                visited[v] = true; 
                dfs(v, adj, visited);
            }
        }
    };

public:
    vector<int> findAllPeople(int n, vector<vector<int>>& meetings, int firstPerson) {
        // 将 meetings 按时间排序
        sort(meetings.begin(), meetings.end(), [](const vector<int>& a, const vector<int>& b) {
            return a[2] < b[2];
        });

        // 根据时间先后，为每个时刻构建一个邻接表,置于列表中。考虑到本就是稀疏图并再次拆分，非常分散，故每个邻接表都用 hash map。
        vector<unordered_map<int, vector<int>>> multiAdj;
        for(int i = 0; i < meetings.size(); ++i){
            if(i == 0 || meetings[i][2] > meetings[i-1][2]) 
                multiAdj.push_back({});
            auto& adj = multiAdj.back();
            int u = meetings[i][0], v = meetings[i][1];
            adj[u].push_back(v);
            adj[v].push_back(u);
        }
        
        vector<bool> visited(n, false);
        visited[0] = true; 
        visited[firstPerson] = true;

        for(const auto& adj : multiAdj){
            // 选取访问过的点 dfs 向外扩散，此处切忌遍历 0～n-1
            for(const auto& p : adj){
                if(visited[p.first])
                    dfs(p.first, adj, visited);            
            }
        }

        // 筛选访问过的点构成结果，即所有知晓秘密的专家
        vector<int> result;
        for(int i = 0; i < n; ++i) {
            if(visited[i]) result.push_back(i);
        }
        return result;
    }
};

###Python3

class Solution:
    def findAllPeople(self, n: int, meetings: List[List[int]], firstPerson: int) -> List[int]:
        # 将 meetings 按时间排序
        meetings.sort(key=lambda x: x[2])

        # 根据时间先后，为每个时刻构建一个邻接表,置于列表中。考虑到本就是稀疏图并再次拆分，非常分散，故每个邻接表都用 hash map。
        multiAdj = []
        for i in range(len(meetings)):
            if i == 0 or meetings[i][2] > meetings[i-1][2]:
                multiAdj.append({})
            adj = multiAdj[-1]
            u, v, time = meetings[i]
            if u not in adj:
                adj[u] = []
            if v not in adj:
                adj[v] = []
            adj[u].append(v)
            adj[v].append(u)
        
        visited = [False] * n
        visited[0] = True
        visited[firstPerson] = True

        def dfs(u: int, adj: Dict[int, List[int]]):
            for v in adj.get(u, []):
                if not visited[v]:
                    visited[v] = True
                    dfs(v, adj)

        for adj in multiAdj:
            # 选取访问过的点 dfs 向外扩散，此处切忌遍历 0～n-1
            for p in adj.keys():
                if visited[p]:
                    dfs(p, adj)
        
        # 筛选访问过的点构成结果，即所有知晓秘密的专家
        return [i for i in range(n) if visited[i]]

###Java

class Solution {
    private void dfs(int u, Map<Integer, List<Integer>> adj, boolean[] visited) {
        if(adj.get(u).isEmpty()) return;

        for (int v : adj.get(u)) {
            if (!visited[v]) {
                visited[v] = true;
                dfs(v, adj, visited);
            }
        }
    }

    public List<Integer> findAllPeople(int n, int[][] meetings, int firstPerson) {
        // 将 meetings 按时间排序
        Arrays.sort(meetings, (a, b) -> Integer.compare(a[2], b[2]));

        // 根据时间先后，为每个时刻构建一个邻接表,置于列表中。考虑到本就是稀疏图并再次拆分，非常分散，故每个邻接表都用 hash map。
        List<Map<Integer, List<Integer>>> multiAdj = new ArrayList<>();
        for (int i = 0; i < meetings.length; i++) {
            if (i == 0 || meetings[i][2] > meetings[i - 1][2]) 
                multiAdj.add(new HashMap<>());
            Map<Integer, List<Integer>> adj = multiAdj.get(multiAdj.size() - 1);
            int u = meetings[i][0], v = meetings[i][1];
            adj.computeIfAbsent(u, k -> new ArrayList<>()).add(v);
            adj.computeIfAbsent(v, k -> new ArrayList<>()).add(u);
        }

        boolean[] visited = new boolean[n];
        visited[0] = true;
        visited[firstPerson] = true;

        for (Map<Integer, List<Integer>> adj : multiAdj) {
            // 选取访问过的点 dfs 向外扩散，此处切忌遍历 0～n-1
            for (int p : adj.keySet()) {
                if (visited[p]) 
                    dfs(p, adj, visited);
            }
        }

        // 筛选访问过的点构成结果，即所有知晓秘密的专家
        List<Integer> result = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            if (visited[i]) result.add(i);
        }
        return result;
    }
}

###Kotlin

class Solution {
    fun findAllPeople(n: Int, meetings: Array<IntArray>, firstPerson: Int): List<Int> {
        // 将 meetings 按时间排序
        meetings.sortBy{ it[2] }

        // 根据时间先后，为每个时刻构建一个邻接表,置于列表中。考虑到本就是稀疏图并再次拆分，非常分散，故每个邻接表都用 hash map。
        val multiAdj = mutableListOf<MutableMap<Int, MutableList<Int>>>()
        for(i in meetings.indices){
            if(i == 0 || meetings[i][2] > meetings[i-1][2]) 
                multiAdj += mutableMapOf()
            val adj = multiAdj.last()
            val (u, v, time) = meetings[i]
            adj.getOrPut(u){ mutableListOf() } += v
            adj.getOrPut(v){ mutableListOf() } += u
        }
        
        val visited = BooleanArray(n)
        visited[0] = true 
        visited[firstPerson] = true

        fun dfs(u: Int, adj: Map<Int, MutableList<Int>>){
            for(v in adj[u] ?: return) 
                if(!visited[v]){
                    visited[v] = true 
                    dfs(v, adj)
                }   
        }

        for(adj in multiAdj){
            // 选取访问过的点 dfs 向外扩散，此处切忌遍历 0～n-1
            for(p in adj.keys){
                if(visited[p])
                    dfs(p, adj)            
            }
        }

        // 筛选访问过的点构成结果，即所有知晓秘密的专家
        return (0..<n).filter{ visited[it] }
    }
}

复杂度

$n$ 为点数（专家数量），$m$ 为边数（meetings 的长度）
考虑排序。

• 时间复杂度: $\Theta(n + m\cdot log\ m)$
• 空间复杂度: $\Theta(n + m)$

推广

以下皆为个人所著，兼顾了职场面试和本硕阶段的学术考试。

• 不同层次的面试算法学习规划
• 附个人题解的双指针题单
• 图论入门
• 图论进阶

点赞关注不迷路。祝君早日上岸，飞黄腾达！