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

798236606

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

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

1. class Solution {
   
2. public:
   
3.     int numOfMinutes(int n, int headID, vector<int>& manager, vector<int>& informTime) {
   
4.         int ans = 0;
   
5. 
   
6.         for (int i = 0; i < n; ++i)
   
7.         {
   
8.             if (!informTime[i])//利用底层员工通知时间为0的设定进行剪枝
   
9.             {
   
10.                 int temp = 0;
    
11.                 for (int j = manager[i]; j != -1; j = manager[j])  temp += informTime[j];
    
12.                 ans = max(ans, temp);
    
13.             }
    
14.         }
    
15. 
    
16.         return ans;
    
17.     }
    
18. };

复制代码

2.自顶向下
建图+BFS

1. class Solution {
   
2. public:
   
3.     vector<int> member[100005];
   
4.    
   
5.     int numOfMinutes(int n, int headID, vector<int>& manager, vector<int>& informTime) {
   
6.         for (int i = 0; i < n; ++i) if (i != headID) member[manager[i]].push_back(i);
   
7.         
   
8.         int ans = 0;
   
9.         queue<pair<int, int>> q;
   
10.         q.push({headID, 0});
    
11.         
    
12.         while (!q.empty())
    
13.         {
    
14.             int id = q.front().first;
    
15.             int temp = q.front().second;
    
16.             q.pop();
    
17.             
    
18.             ans = max(ans, temp);
    
19. 
    
20.             for (int each: member[id]) q.push({each, temp + informTime[id]});
    
21.         }
    
22.         
    
23.         return ans;
    
24.     }
    
25. };

复制代码