Leetcode 1376. Time Needed to Inform All Employees (python+cpp)

题目

解法1：BFS

class Solution:def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:graph = collections.defaultdict(list)# s:subordinates,m:direct managerfor s,m in enumerate(manager):graph[m].append(s)q = collections.deque()q.append((headID,0))ans = 0;while q:curr_m,time = q.popleft()if curr_m not in graph:ans = max(ans,time)for curr_s in graph[curr_m]:q.append((curr_s,informTime[curr_m]+time))return ans

C++版本
这边表示图既可以用unordered_map也可以用vector和array结合。unordered_map会稍微慢一点，因为他的查找操作并不是严格O(1)的

class Solution {
    
public:int numOfMinutes(int n, int headID, vector<int>& manager, vector<int>& informTime) {
    // constuct an array with size n, every element is a vector with variable sizevector<int> graph[n];// unordered_map<int,vector<int>> graph; use this to construct the graph also worksfor(int i=0;i<manager.size();i++){
    if(manager[i] != -1){
    graph[manager[i]].push_back(i);}}queue<pair<int,int>> q;q.push({
    headID,0});int ans = 0;while(!q.empty()){
    pair<int,int> curr = q.front();q.pop();// if(graph.find(curr.first) == graph.end()) for map approachif(graph[curr.first].size() == 0){
    ans = max(ans,curr.second);}for(auto curr_s:graph[curr.first]){
    q.push({
    curr_s,curr.second+informTime[curr.first]});}}return ans;}
};

解法2：dfs

这道题dfs和bfs复杂度一致，每个节点都只需访问一遍

class Solution:def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:def dfs(m,curr_time,max_time):if not graph[m]:return max(curr_time,max_time)for s in graph[m]:max_time= dfs(s,curr_time+informTime[m],max_time)return max_timegraph = collections.defaultdict(list)for s,m in enumerate(manager):graph[m].append(s)return dfs(headID,0,0)

二刷dfs

top-bottom写法

class Solution {
    
public:int helper(int node, unordered_map<int,vector<int>>& g,vector<int>& informTime){
    if(!g.count(node)) return 0;int res = 0;for(auto& sub : g[node]){
    res = max(res,helper(sub,g,informTime)+informTime[node]);}return res;}int numOfMinutes(int n, int headID, vector<int>& manager, vector<int>& informTime) {
    unordered_map<int,vector<int>> g;for(int i=0;i<manager.size();i++){
    if(manager[i] == -1){
    continue;}g[manager[i]].push_back(i);}return helper(headID,g,informTime);}
};

bottom-up写法：从每个员出发，计算从这个员工到根员工的时间，利用manager数组和informtime数组来进行memorization，避免重复访问

class Solution {
    
public:int helper(int node, vector<int>& manager,vector<int>& informTime){
    if(manager[node] == -1){
    return informTime[node];}else{
    informTime[node] += helper(manager[node],manager,informTime);manager[node] = -1;}return informTime[node];}int numOfMinutes(int n, int headID, vector<int>& manager, vector<int>& informTime) {
    int res = 0;for(int i=0;i<manager.size();i++){
    res = max(res,helper(i,manager,informTime));}return res;}
};

时间复杂度:O(n)
空间复杂度：O(n)