LeetCode 5354. 通知所有员工所需的时间

798236606

传送门：https://leetcode-cn.com/problems ... form-all-employees/

解：
1.自底向上
从每一个底层员工向上找上司，类似于并查集的查找。由于每次都要遍历一遍到老板的路径，时间效率不高。

class Solution {
public:
    int numOfMinutes(int n, int headID, vector<int>& manager, vector<int>& informTime) {
        int ans = 0;

        for (int i = 0; i < n; ++i)
        {
            if (!informTime[i])//利用底层员工通知时间为0的设定进行剪枝
            {
                int temp = 0;
                for (int j = manager[i]; j != -1; j = manager[j])  temp += informTime[j];
                ans = max(ans, temp);
            }
        }

        return ans;
    }
};

2.自顶向下
建图+BFS

class Solution {
public:
    vector<int> member[100005];
    
    int numOfMinutes(int n, int headID, vector<int>& manager, vector<int>& informTime) {
        for (int i = 0; i < n; ++i) if (i != headID) member[manager[i]].push_back(i);
        
        int ans = 0;
        queue<pair<int, int>> q;
        q.push({headID, 0});
        
        while (!q.empty())
        {
            int id = q.front().first;
            int temp = q.front().second;
            q.pop();
            
            ans = max(ans, temp);

            for (int each: member[id]) q.push({each, temp + informTime[id]});
        }
        
        return ans;
    }
};